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

UVA 247 - Calling Circles

#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);
    }
}

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

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

Factorization with prime Sieve

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