Cod sursa(job #2087043)

Utilizator b_aurelBanica Aurel b_aurel Data 12 decembrie 2017 20:37:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100005;
vector <int> G[NMAX];
vector <int> Gt[NMAX], ctc[NMAX];
int nctc, N, M, i, x, y, k, j;
int viz[NMAX], prima[NMAX];
void DFS(int x)
{
    viz[x] = 1;
    for (int i =0; i < G[x].size(); i++)
        if (viz[G[x][i]]==0)
        {
            DFS(G[x][i]);
        }
    prima[++k]=x;
}

void DFP(int x)
{
    viz[x] = 0;
    ctc[nctc].push_back(x);
    for (int i =0; i < Gt[x].size(); i++)
        if (viz[Gt[x][i]]==1) DFP(Gt[x][i]);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    scanf("%d%d\n",&N, &M);
    for (i=1; i <= M; i++)
    {
        scanf("%d%d\n", &x, &y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    k = 0;
    for (i = 1; i <= N; i++)
        if  (viz[i] == 0) DFS(i);

    for (i= N; i >= 1; i-- )
        if (viz[prima[i]] == 1)
        {
            nctc++;
            DFP(prima[i]);
        }
    printf("%d\n", nctc);
    for (i = 1; i <= nctc; i++)
    {
        for (j = 0; j < ctc[i].size(); j++)
            printf("%d ",ctc[i][j]);
        printf("\n");
    }
    return 0;
}