Cod sursa(job #2255742)

Utilizator flibiaVisanu Cristian flibia Data 7 octombrie 2018 15:29:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

//ifstream in("tst.in");
ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m, x, y, vf, cnt, st[100100];
vector <int> v[100100], vv[100100], s[100100];
bool viz[100100];

void dfs(int x){
	viz[x] = 1;
	for(auto y : v[x])
		if(!viz[y])
			dfs(y);
	st[++vf] = x;
}

void dfs2(int x){
	viz[x] = 0;
	s[cnt].push_back(x);
	for(auto y : vv[x])
		if(viz[y])
			dfs2(y);
}

int main(){
	in >> n >> m;
	while(m--){
		in >> x >> y;
		v[x].push_back(y);
		vv[y].push_back(x);
	}
	for(int i = 1; i <= n; i++)
		if(!viz[i])
			dfs(i);
	for(; vf; vf--)
		if(viz[st[vf]]){
			cnt++;
			dfs2(st[vf]);
		}
	out << cnt;
	for(int i = 1; i <= cnt; i++){
		out << '\n';
		for(auto j : s[i])
			out << j << ' ';
	}
	return 0; 
}