Cod sursa(job #1111001)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 18 februarie 2014 16:11:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <vector>

#define Nmax 100005

using namespace std;

int N, M, St[Nmax], Viz[Nmax], nr;
vector <int> G[Nmax], Gt[Nmax], Sol[Nmax];

void Citire()
{
    int x, y;
    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);
    }
}

void DFS(int nod)
{
    vector <int> :: iterator it;
    Viz[nod] = 1;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
        if (!Viz[*it])
            DFS(*it);
    St[++St[0]] = nod;
}

void DFS2(int nod)
{
    vector <int> :: iterator it;
    Viz[nod] = 1;
    Sol[nr].push_back(nod);
    for (it = Gt[nod].begin(); it != Gt[nod].end(); ++it)
        if (!Viz[*it])
            DFS2(*it);
}

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

    Citire();
    for (int i = 1; i <= N; ++i)
        if (!Viz[i])
            DFS(i);
    for (int i = 1; i <= N; ++i)
        Viz[i] = 0;
    for (int i = St[0]; i >= 1; --i)
        if (!Viz[St[i]])
        {
            nr++;
            DFS2(St[i]);
        }
    printf("%d\n", nr);
    for (int i = 1; i <= nr; ++i)
    {
        for (vector <int> :: iterator it = Sol[i].begin(); it != Sol[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}