Cod sursa(job #1572336)

Utilizator gabib97Gabriel Boroghina gabib97 Data 18 ianuarie 2016 21:05:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int i,n,m,nr,postordine[100001],x,y,t,j;
bool o[100001];
vector<int> G[100001],GT[100001],q[100001];
void DFS(int s)
{
    int i,z=G[s].size();
    o[s]=1;
    for (i=0;i<z;i++)
        if (!o[G[s][i]]) DFS(G[s][i]);
    postordine[++nr]=s;
}
void DFST(int s)
{
    int i,z=GT[s].size();
    o[s]=0;
    for (i=0;i<z;i++)
        if (o[GT[s][i]]) DFST(GT[s][i]);
    q[t].push_back(s);
}
int main()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (!o[i]) DFS(i);
    for (i=nr;i>=1;i--)
        if (o[postordine[i]]) ++t,DFST(postordine[i]);
    printf("%i\n",t);
    for (i=1;i<=t;i++)
    {
        for (j=0;j<q[i].size();j++) printf("%i ",q[i][j]);
        printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}