Cod sursa(job #1642074)

Utilizator gapdanPopescu George gapdan Data 9 martie 2016 12:35:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 100005

using namespace std;

vector<int>v[NMAX],v1[NMAX],C[NMAX];
int sol[NMAX],viz[NMAX];
int n,i,j,k,m,x,y,ctc;

void DFS(int nod)
{
    int i;
    viz[nod]=1;
    for(i=0;i<v[nod].size();++i)
        if(viz[v[nod][i]] == 0) DFS(v[nod][i]);
    sol[++k]=nod;
}

void DFS1(int nod)
{
    int i;
    viz[nod]=1;
    C[ctc].push_back(nod);
    for(i=0;i<v1[nod].size(); ++i)
    {
        if(viz[v1[nod][i]] == 0) DFS1(v1[nod][i]);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v1[y].push_back(x);
    }

    for(i=1;i<=n;++i)
        if(viz[i] == 0) DFS(i);

    memset(viz,0,sizeof(viz));
    for(i=k;i>=1;--i)
    {
        if(viz[sol[i]] == 0)
        {
           ++ctc;
          DFS1(sol[i]);
        }
    }
    printf("%d\n",ctc);
    for(i=1;i<=ctc;++i)
    {
        sort(C[i].begin(),C[i].end());
        for(j=0;j<C[i].size();++j) printf("%d ",C[i][j]);
        printf("\n");
    }
    return 0;
}