Cod sursa(job #1686249)

Utilizator MihaiEMihaiE MihaiE Data 12 aprilie 2016 10:02:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <vector>
#include <cstring>
#define nmax 100010

using namespace std;

int n,m,x,y,nr;
bool fr[nmax];
vector <int> g[nmax],gt[nmax],sol,c[nmax];

void dfs1(int nod)
{
    fr[nod]=true;

    for (int i=0;i<(int)g[nod].size();i++)
        if (!fr[g[nod][i]]) dfs1(g[nod][i]);

    sol.push_back(nod);
}

void dfs2(int nod)
{
    fr[nod]=true;

    for (int i=0;i<(int)gt[nod].size();i++)
        if (!fr[gt[nod][i]]) dfs2(gt[nod][i]);

    c[nr].push_back(nod);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d %d",&n,&m);

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

    for (int i=1;i<=n;i++)
        if (!fr[i]) dfs1(i);

    memset(fr,0,sizeof(fr));

    for (int i=sol.size()-1;i>=0;i--)
        if (!fr[sol[i]]) nr++,dfs2(sol[i]);

    printf("%d\n",nr);

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

    return 0;
}