Articulation Bridge Print

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[100005];
vector<pair<int,int> >bridge;
int id[100005],low[1000005],vis[100005],somoy;
void dfs(int uu,int par)
{
    low[uu]=id[uu]=++somoy;
    vis[uu]=1;
    for(int ii=0;ii<vec[uu].size();ii++)
    {
        int vv=vec[uu][ii];
        if(vv==par)
        {
            continue;
        }
        if(vis[vv]==0)
        {
            dfs(vv,uu);
            low[uu]=min(low[uu],low[vv]);
            if(id[uu]<low[vv])
            {
                bridge.push_back({min(uu,vv),max(uu,vv)});
            }
        }
        else
        {
            low[uu]=min(low[uu],id[vv]);
        }
    }
}
main()
{
    timesave;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        int i,u,v;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=m;i++)
        {
            cin>>u>>v;
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        somoy=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                dfs(i,-1);
            }
        }
        for(i=0;i<bridge.size();i++)
        {
            cout<<bridge[i].first<<" "<<bridge[i].second<<endl;
        }
        bridge.clear();
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
        }
    }
}


/*
INPUT:
6 5
1 2
2 3
2 4
2 5
4 5

4 2
1 2
2 3


OUTPUT:
2 3
1 2

1 2
2 3
*/

Articulation Point

Problem Link:
https://www.spoj.com/problems/SUBMERGE/en/

Hints: Find how many articulation point in the graph

Solution

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e4+4;
vector<int>vec[maxn];
bool visit[maxn];
int parent[maxn];
int low[maxn];
set<int>ap;
int disc[maxn];
int timee;
void ArticulationPoint(int u)
{
    int child=0;
    visit[u]=1;
    disc[u]=low[u]=++timee;
    for(int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if(visit[v]==0)
        {
            child++;
            parent[v]=u;
            ArticulationPoint(v);
            low[u]=min(low[u],low[v]);
            if(parent[u]==-1&&child>1)
                ap.insert(u);
            if(parent[u]!=-1&&low[v]>=disc[u])
                ap.insert(u);
        }
        else if(v!=parent[u])
            low[u]=min(low[u],disc[v]);
    }
}
int main()
{
    //freopen("t.txt","r",stdin);
    int n,m,u,v;
    while(scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
            break;
        memset(parent,-1,sizeof parent);
        memset(visit,0,sizeof visit);
        for(int i=0; i<n+1; i++)
            vec[i].clear();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        for(int i=0; i<n; i++)
        {
            if(visit[i]==0)
            {
                timee=0;
                ArticulationPoint(i);
            }
        }
        printf("%d\n",ap.size());
        ap.clear();
    }
}

UVA 11709 - Trust groups

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[1010],ultavec[1010],dhokalam;
int vis[1010];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<ultavec[u].size(); ii++)
    {
        int v=ultavec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        getchar();
        string s,s1;
        int i;
        map<string,int>mp;
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            ultavec[i].clear();
        }
        dhokalam.clear();
        for(i=1;i<=n;i++)
        {
            getline(cin,s);
            mp[s]=i;
        }
        for(i=1;i<=m;i++)
        {
            getline(cin,s);
            getline(cin,s1);
            int a=mp[s],b=mp[s1];
            vec[a].push_back(b);
            ultavec[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        cout<<cnt<<endl;

    }

}

UVA 12926 - Trouble in Terrorist Town

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[5050],ultavec[5050],dhokalam;
int vis[5050],ar[5050][5050];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<ultavec[u].size(); ii++)
    {
        int v=ultavec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,a,b;
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
            ultavec[i].clear();
            for(j=1;j<=n;j++)
            {
                ar[i][j]=1;
                ar[j][i]=1;

            }
        }
        dhokalam.clear();
        for(i=1;i<=m;i++)
        {
            sf2(a,b);
            ar[a][b]=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(ar[i][j])
                {
                    vec[i].push_back(j);
                    ultavec[j].push_back(i);
                }
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                //cout<<dhokalam[i]<<endl;
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        int cost;
        sf(cost);
        pf(cnt*cost);
        nl;

    }

}

12645 - Water Supply (SCC)

Blog Link for Hints:
https://asdfcoding.wordpress.com/2014/04/24/12645-water-supply-uva/



///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
vector<int>vec[1100],dhokalam;
int vis[1100];
void dfs(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs(v);
    }
    dhokalam.push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int ii=0; ii<vec[u].size(); ii++)
    {
        int v=vec[u][ii];
        if(vis[v]==0)
            dfs1(v);
    }
}
main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int i,a,b,cnt=0;
        for(i=0; i<=n; i++)
        {
            vec[i].clear();
        }
        dhokalam.clear();
        for(i=1; i<=m; i++)
        {
            cin>>a>>b;
            if(b==0)
                continue;
            vec[a].push_back(b);
        }

        memset(vis,0,sizeof(vis));
        for(i=0; i<=n; i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=dhokalam.size()-1; i>=0; i--)
        {
            if(vis[dhokalam[i]]==0)
            {
                //cout<<dhokalam[i]<<endl;
                cnt++;
                dfs1(dhokalam[i]);
            }
        }
        cout<<cnt-1<<endl;

    }

}

Light oj Problem no:1003 ( Detect Cycle or Not)

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1003



///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld",a,b)
#define pf3(a,b,c) printf("lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
#define M 100005
int visited[M], cycle = 0;
vector<int>vec[M];
void dfs(int u)
{
    int i;
    visited[u]=1;
    if (cycle==1)
        return;
    for (i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if (visited[v]==1)
        {
            cycle=1;
            return;
        }
        else if (visited[v]==0)
        {
            dfs(v);
        }
    }
    visited[u]=2;
}
main()
{
    int ts,cs=1;
    cin>>ts;
    while(ts--)
    {

        int m;
        cin>>m;
        int i,u,v,cnt=1;
        string s,s1;
        map<string,int>mp;
        for (i=0; i<10010; i++)
        {
            vec[i].clear();
            visited[i]=0;
        }
        for(i=1; i<=m; i++)
        {
            cin>>s>>s1;
            if(mp[s]==0)
            {
                mp[s]=cnt;
                cnt++;
            }
            u=mp[s];
            if(mp[s1]==0)
            {
                mp[s1]=cnt;
                cnt++;
            }
            v=mp[s1];
            vec[u].push_back(v);
        }
        cycle=0;
        for(i=1; i<=cnt; i++)
        {
            if(visited[i]==0)
            {
                dfs(i);
            }
        }
        if(cycle==1)
        {
            printf("Case %d: No\n",cs++);
        }
        else
            printf("Case %d: Yes\n",cs++);
    }
}