Cod sursa(job #2091722)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 20 decembrie 2017 09:19:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,nr,Minus[100001];
bool Plus[100001];
vector <int> G[100001],Gt[100001],ctc[100001];
stack <int> stiva;
void DFS1(int nod){
    Plus[nod]=1;
    for(int i=0;i<(int)G[nod].size();++i)
        if(Plus[G[nod][i]]==0)
            DFS1(G[nod][i]);
    stiva.push(nod);
}
void DFS2(int nod){
    Minus[nod]=nr;
    for(int i=0;i<(int)Gt[nod].size();++i)
        if(Minus[Gt[nod][i]]==0)
            DFS2(Gt[nod][i]);
}
int main(){
    int x,y;
    f>>N>>M;
    while(M--){
        f>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(int i=1;i<=N;++i)
        if(Plus[i]==0)
            DFS1(i);
    while(!stiva.empty()){
        x=stiva.top();
        stiva.pop();
        if(Minus[x]==0){
            ++nr;
            DFS2(x);
        }
    }
    for(int i=1;i<=N;++i)
        ctc[Minus[i]].push_back(i);
    g<<nr<<'\n';
    for(int i=1;i<=nr;++i){
        for(int j=0;j<(int)ctc[i].size();++j)g<<ctc[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}