Cod sursa(job #2664582)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 28 octombrie 2020 20:57:16
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

struct nod{
	bool viz;
	vector<int> in;
	vector<int> out;
	int who;
};
vector<nod> g;

stack<int> s;

void dfs1(int root){
	g[root].viz=1;
	for(auto it:g[root].out){
		if(!g[it].viz){
			s.push(it);
			dfs1(it);
		}
	}
}

void dfs2(int root, int x){
	g[root].who=x;
	for(auto it:g[root].in){
		if(!g[it].who){
			dfs2(it, x);
		}
	}
}

int main(){
	int n, m;
	fin>>n>>m;
	g.resize(n+1);
	for(int i=1;i<=m;++i){
		int a, b;
		fin>>a>>b;
		g[a].out.push_back(b);
		g[b].in.push_back(a);
	}
	for(int i=1;i<=n;++i) if(!g[i].viz) dfs1(i);
	while(!s.empty()){
		while(!s.empty()&&g[s.top()].who) s.pop();
		if(s.empty()) break;
		dfs2(s.top(), s.top());
		s.pop();
	}
	unordered_map<int, vector<int>> ma;
	for(int i=1;i<=n;++i){
		ma[g[i].who].push_back(i);
	}
	fout<<ma.size()<<"\n";
	for(auto it:ma){
		for(auto it2:it.second){
			fout<<it2<<" ";
		}
		fout<<"\n";
	}
}