Cod sursa(job #781811)

Utilizator stefanzzzStefan Popa stefanzzz Data 25 august 2012 09:33:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,x,y,nrctc;
vector<int> G[MAXN],GT[MAXN],ctc[MAXN],post;
bool uz[MAXN];

void DFS(int p);
void DFS_T(int p);

int main()
{
    int i,j;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);}
    for(i=1;i<=n;i++)
        if(!uz[i])
            DFS(i);
    for(i=1;i<=n;i++)
        uz[i]=0;
    for(i=post.size()-1;i>=0;i--){
        if(!uz[post[i]]){
            nrctc++;
            DFS_T(post[i]);}}
    g<<nrctc<<'\n';
    for(i=1;i<=nrctc;i++){
        for(j=0;j<ctc[i].size();j++)
            g<<ctc[i][j]<<' ';
        g<<'\n';}
    f.close();
    g.close();
    return 0;
}

void DFS(int p){
    int i;
    uz[p]=1;
    for(i=0;i<G[p].size();i++)
        if(!uz[G[p][i]])
            DFS(G[p][i]);
    post.push_back(p);}

void DFS_T(int p){
    int i;
    uz[p]=1;
    ctc[nrctc].push_back(p);
    for(i=0;i<GT[p].size();i++)
        if(!uz[GT[p][i]])
            DFS_T(GT[p][i]);}