Cod sursa(job #641515)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 28 noiembrie 2011 18:09:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,i,m,a,b,t=0,tfinal[100001],s[200001],nctc;
vector <int> A[100001];
vector <int> B[100001];
bitset <100001> fr;
bitset <100001> fr2;
bitset <100001> fr3;
void dfs(int nod) {
    vector <int>::iterator it;
    fr[nod]=1;
    tfinal[nod]=++t;
    for (it=A[nod].begin();it!=A[nod].end();it++)
        if (fr[*it]==0) dfs(*it);
    tfinal[nod]=++t;
    s[t]=nod;
    return;
}
void dfs2(int nod) {
    vector <int>::iterator it;
    fr2[nod]=1;
    for (it=B[nod].begin();it!=B[nod].end();it++)
        if (fr2[*it]==0) dfs2(*it);
    return ;
}
void dfs3(int nod) {
    vector <int>::iterator it;
    fr3[nod]=1;
    g << nod << ' ';
    for (it=B[nod].begin();it!=B[nod].end();it++)
        if (fr3[*it]==0) dfs3(*it);
    return ;
}

int main () {
    f >> n >> m;
    for (i=1;i<=m;i++) {
        f >> a >> b;
        A[a].push_back(b);
        B[b].push_back(a);
    }
    for (i=1;i<=n;i++)
        if (fr[i]==0) dfs(i);
    for (i=t;i>=1;i--)
        if (fr2[s[i]]==0 && s[i]>0) {dfs2(s[i]);nctc++;}
    g << nctc << '\n';
    for (i=t;i>=1;i--)
        if (fr3[s[i]]==0 && s[i]>0) {dfs3(s[i]);g << '\n';}
    f.close();g.close();
    return 0;
}