Cod sursa(job #519172)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 4 ianuarie 2011 12:36:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
//Kosaraju
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 100005
using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");

vector<int> G[MAX],GT[MAX];
vector<int> v[MAX];
vector<int> p;
vector<int> tip;
stack<int>S;
int nr;

void DFP(int nod)
{
    int i,x;
    p[nod]=true;
    x=G[nod].size();
    for(i=0;i<x;i++)
        if(!p[G[nod][i]]) DFP(G[nod][i]);
    S.push(nod);
}

void DFM(int nod)
{
    int i,x;
    tip[nod]=nr;
    x=GT[nod].size();
    for(i=0;i<x;i++)
        if(!tip[GT[nod][i]]) DFM(GT[nod][i]);

}
int main()
{
    int n,m,x,y,i,j;
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    p.resize(n+1);
    p.assign(p.size(),false);
    for(i=1;i<=n;i++)
    if(p[i]==false)
        DFP(i);
    tip.resize(n+1);
    tip.assign(tip.size(),0);
    for(;!S.empty();S.pop())
        if(!tip[S.top()])
        {
            nr++;
            DFM(S.top());
        }
    fo<<nr<<"\n";
    for(i=1;i<=n;i++) v[tip[i]].push_back(i);
    for(i=1;i<=nr;i++)
    {
        x=v[i].size();
        for(j=0;j<x;j++) fo<<v[i][j]<<" ";
        fo<<"\n";
    }
}