Cod sursa(job #806130)

Utilizator Theorytheo .c Theory Data 1 noiembrie 2012 21:23:11
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
#define nmax 100008

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, nr, comp_conexe;
vector <int> CTC[1000], G[nmax], Gt[nmax];
bool see[nmax];
int ord[nmax];

void read()
{
    fin >>N>> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x>> y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}

void DFS(int x)
{
    see[x] = true;
    for(int i = 0; i < G[x].size(); i++)
    {
        if(see[G[x][i]] == false)
            DFS(G[x][i]);

    }
    ord[++nr] = x;
}

void DFS2(int x)
{
    see[x] = false;
    CTC[comp_conexe].push_back(x);

    for(int i = 0; i < Gt[x].size(); i++)
    {
        if(see[Gt[x][i]])
            DFS2(Gt[x][i]);
    }
}

void display()
{
    fout << comp_conexe <<'\n';

     for(int i = 1; i <= comp_conexe; i++){
         for(int j = 0 ;j < CTC[i].size(); j++)
            fout << CTC[i][j] <<" ";
        fout << '\n';
     }

}

int main()
{
    read();
    for(int i = 1; i <= N; i++)
        if(see[i] == false)
            DFS(i);

    for(int i = N; i > 0 ;i--)
    {
        if(see[ord[i]] == true)
        {
            comp_conexe++;
            DFS2(ord[i]);
        }

    }
    display();



    fin.close();
    return 0;
}