Cod sursa(job #1300760)

Utilizator OctaDuiu Octavian Octa Data 24 decembrie 2014 22:31:31
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<vector>
using namespace std;
vector < int > g[50003];
vector < int > t[50003];
vector < int > v[50003];
bool u[50003];
int n,m,i,x,y,p[50003];

void dfs(int nod)
{
    u[nod]=true;

    for(int k=0;k<g[nod].size();++k)
        if(!u[g[nod][k]]) dfs(g[nod][k]);

    p[++x]=nod;
}

void dfs_t(int nod)
{
    u[nod]=false;
    v[y].push_back(nod);

    for(int k=0;k<t[nod].size();++k)
        if(u[t[nod][k]]) dfs_t(t[nod][k]);
}
int main()
{
    freopen("ctc.in","r",stdin);freopen("ctc.out","w",stdout);

    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
        {
            int x,y;
            scanf("%d %d",&x,&y);
             g[x].push_back(y);
             t[y].push_back(x);
        }

    x=0;
    for(i=1;i<=n;++i)
        if(!u[i]) dfs(i);

    y=0;
    for(i=n;i>0;--i)
    {
        if(u[p[i]])
        {
            ++y;
            dfs_t(p[i]);
        }
    }

    printf("%d\n",y);
    for(i=1;i<=y;++i)
    {
        for(int j=0;j<v[i].size();++j)
            printf("%d ",v[i][j]);

      printf("\n");
    }
    return 0;
}