Cod sursa(job #1650457)

Utilizator ZenusTudor Costin Razvan Zenus Data 11 martie 2016 18:27:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 100009;

int marked[nmax] , st[nmax];
vector < int > g[nmax] , t[nmax] , ctc[nmax];
int top , S , i , n , m , a , b , j;

void dfG(int x)
{
    marked[x] = true;
    for (int i = 0 ; i < g[x].size() ; ++i)
    {
        int y = g[x][i];
        if (marked[y]) continue;

        dfG(y);
    }
    st[++top] = x;
}

void dfT(int x)
{
    ctc[S].push_back(x);
    marked[x] = false;

    for (int i = 0 ; i < t[x].size() ; ++i)
    {
        int y = t[x][i];
        if (!marked[y]) continue;

        dfT(y);
    }
}

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

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

for (i = 1 ; i <= m ; ++i)
{
    scanf("%d" , &a);
    scanf("%d" , &b);

    g[a].push_back(b);
    t[b].push_back(a);
}

for (i = 1 ; i <= n ; ++i)
if (!marked[i]) dfG(i);

while (top)
{
    if (marked[st[top]])
    {
        ++S;
        dfT(st[top]);
    }
    top--;
}

printf("%d\n" , S);
for (i = 1 ; i <= S ; ++i)
{
    for (j = 0 ; j < ctc[i].size() ; ++j)
    printf("%d " , ctc[i][j]);
    printf("\n");
}

return 0;
}