Cod sursa(job #1514276)

Utilizator greenadexIulia Harasim greenadex Data 30 octombrie 2015 22:10:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "ctc",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MAX = 1e5 + 5;

vector<int> gr[MAX], invgr[MAX], perm, vaca[MAX];
int n, m;
bitset<MAX> viz;

void dfs(int node, vector<int> gr[], bool vaca){
	viz[node] = 1;

	if (vaca)
		fout << node << ' ';

	for (auto it: gr[node])
		if (!viz[it])
			dfs(it, gr, vaca);

	perm.pb(node);
}

int main() {
	fin >> n >> m;
	for(int a, b; m; m--) {
		fin >> a >> b;
		gr[a].pb(b);
		invgr[b].pb(a);
	}

	for (int i = 1; i <= n; i++) 
		if (!viz[i])
			dfs(i, gr, false);

	viz = 0;
	int cnt = 0;
	for (int i = n - 1; i >= 0; i--) 
		if (!viz[perm[i]]){
			dfs(perm[i], invgr, false);
			cnt++;
		}
	
	viz = 0;
	fout << cnt << '\n';
	for (int i = n - 1; i >= 0; i--)
		if (!viz[perm[i]]) {
			dfs(perm[i], invgr, true);
			fout << '\n';
		}

	return 0;
}