Cod sursa(job #2744498)

Utilizator NashikAndrei Feodorov Nashik Data 24 aprilie 2021 19:27:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <int> c[100005],rev[100005],v[100005];
int comp,cnt,cont,order[100005],viz[100005];
void dfs(int nod){
    viz[nod]=1;
    for(auto u:v[nod]){
        if(viz[u]==0){
            dfs(u);
        }
    }
    order[++cont]=nod;
}
void dfs1(int nod){
    viz[nod]=1;
    c[comp].push_back(nod);
    for(auto u:rev[nod]){
        if(viz[u]==0){
            dfs1(u);
        }
    }
}
int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n,m,a,b;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        rev[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
        if(viz[i]==0)
            dfs(i);
	}
	for(int i=1;i<=n;i++){
        viz[i]=0;
	}
	for(int i=n;i>=1;i--){
        if(viz[order[i]]==0){
            comp++;
            dfs1(order[i]);
        }
	}
	cout<<comp<<"\n";
	for(int i=1;i<=comp;i++){
        for(auto u:c[i]){
            cout<<u<<" ";
        }
        cout<<"\n";
	}
}