শনিবার, ২২ জুলাই, ২০১৭

Strongly connencted component code in c++

Nice tutorial :- tushar roy 
Link:- https://www.youtube.com/watch?v=RpgcYiky7uw&t=849s
1 no:- uva 247 no problem code (by mine)
#include<bits/stdc++.h>
#define mx 105
using namespace std;
vector<int>vec[mx],ultavec[mx];
vector<string>allnames;
vector<int>dhokalam;
map<string,int>mp;
int vis[mx],ar[mx],newline=0,cs=1,n,m;
void dfs(int u)
{
    vis[u]=1;
    int v,j;
    for(j=0;j<vec[u].size();j++)
    {
        v=vec[u][j];
        if(vis[v]==0)
        {
            dfs(v);
        }
    }
    dhokalam.push_back(u);
}
void dfs2(int u,int c)
{
    vis[u]=0;
    int v,j;
    ar[u]=c;
    for(j=0;j<ultavec[u].size();j++)
    {
        v=ultavec[u][j];
        if(vis[v]==1)
        {
            dfs2(v,c);
        }
    }
}
void print(int len)
{
    if(newline!=0)
        printf("\n");
    newline=1;
    int i1,j;
    int spc=0;
    printf("Calling circles for data set %d:\n",cs++);
    for(i1=1;i1<=len;i1++)
    {
        spc=0;
        for(j=1;j<=n;j++)
        {
            if(ar[j]==i1)
            {
                if(spc==1)
                {
                    printf(", ");
                }
                spc=1;
                cout<<allnames[j-1];
            }
        }
        printf("\n");
    }
}
main()
{
    while(cin>>n>>m)
    {
        if ( n == 0 && m == 0 ) break;
        int i,cnt=1;;
        for(i=0;i<=mx;i++)
        {
            vec[i].clear();
            ultavec[i].clear();
        }
        allnames.clear();
        mp.clear();
        newline=0;
        string s,s1;
        for(i=1;i<=m;i++)
        {
            cin>>s>>s1;
            if(mp[s]==0)
            {
                mp[s]=cnt++;
                allnames.push_back(s);
            }
            if(mp[s1]==0)
            {
                mp[s1]=cnt++;
                allnames.push_back(s1);
            }
            vec[mp[s]].push_back(mp[s1]);
            ultavec[mp[s1]].push_back(mp[s]);
        }
        for(i=1;i<cnt;i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
            }
        }
        int k=dhokalam.size()-1;
        cnt=0;
        for(i=k;i>=0;i--)
        {
            if(vis[dhokalam[i]]==1)
            {
                dfs2(dhokalam[i],++cnt);
            }
        }
        print(cnt);
    }
}

2 no: uva 247 no problem code (from internet)
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define N 100
using namespace std;
map<string, int> names;
vector<string> rNames;

vector <int> edges [N];
vector <int> rEdges [N];    // reversed edges
vector <int> sortedNode;
bool vis [N];
int comp [N];               // component number of a node
int cases = 0;
bool blank = false;
int n, m;
void reset ()
{
    int i;
    for (i = 0; i < N; i++ )
    {
        edges [i].clear();
        rEdges [i].clear();
    }
    sortedNode.clear();
    names.clear();
    rNames.clear();
    memset (vis, false, sizeof vis);
}
void dfs1 (int x)
{
    vis [x] = true;
    int u;
    for (u = 0; u < edges [x].size(); u++ )
    {
        if (vis[edges[x][u]]==0)
            dfs1(edges [x] [u]);
    }
    sortedNode.push_back(x);
}
void dfs2 (int x, int c)
{
    vis [x] = false;
    comp [x] = c;
    int u;
    for (u = 0; u < rEdges [x].size(); u++ )
    {
        if (vis[rEdges [x][u]])
            dfs2(rEdges [x] [u], c);
    }
}
void printOutput(int compLen)
{
    if (blank) printf ("\n");
    blank = true;
    printf ("Calling circles for data set %d:\n", ++cases);
    bool space;
    int i,j;
    for (i = 1; i <= compLen; i++ )
    {
        space = false;
        for (j=0;j<n;j++)
        {
            if (comp [j + 1] == i)
            {
                if (space) printf (", ");
                space = true;
                cout << rNames[j];
            }
        }
        printf ("\n");
    }
}
int main ()
{
    while (scanf ("%d %d", &n, &m))
    {
        if ( n == 0 && m == 0 ) break;
        reset();
        int i,namesLen=0;
        string name1, name2;
        for(i=0;i<m;i++)
        {
            cin >> name1 >> name2;
            if (names [name1]==0)
            {
                ++namesLen;
                names [name1] = namesLen;
                rNames.push_back(name1);
            }
            if (names [name2]==0)
            {
                ++namesLen;
                names [name2] = namesLen;
                rNames.push_back(name2);
            }
            edges [names [name1]].push_back(names [name2]);
            rEdges [names [name2]].push_back(names [name1]);
        }
        for(i=0;i<namesLen;i++)
        {
            if (!vis [i + 1])
            {
                dfs1(i + 1);
            }
        }
        int compId = 0;
        for(i=sortedNode.size()-1;i>=0;i--)
        {
            if ( vis [sortedNode [i]] )
                dfs2(sortedNode [i], ++compId);
        }
        printOutput(compId);
    }
    return 0;
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...