Cod sursa(job #2506598)

Utilizator HumikoPostu Alexandru Humiko Data 8 decembrie 2019 14:48:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <bitset>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("ctc.in");
ofstream cout ("ctc.out");	

static const int NMAX = 1e5+5;

stack <int> nodes;

bitset <NMAX> f;

vector <int> graph[NMAX];
vector <int> reversedGraph[NMAX];
vector <int> ctc[NMAX];

void dfs (int vertex) {
	f[vertex] = 1;

	for ( auto x:graph[vertex] ) {
		if ( !f[x] ) {
			dfs(x);
		}
	}

	nodes.push(vertex);
}

void reverseDfs(int vertex, int k) { 
	f[vertex] = 1;

	for ( auto x:reversedGraph[vertex] ) {
		if ( !f[x] ) {
			reverseDfs(x, k);
		}
	}

	ctc[k].push_back(vertex);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin>>n>>m;

	for ( int i = 1; i <= m; ++i ) {
		int x, y;
		cin>>x>>y;
		graph[x].push_back(y);
		reversedGraph[y].push_back(x);
	}

	for ( int i = 1; i <= n; ++i ) {
		if ( !f[i] ) {
			dfs(i);
		}
	}

	for ( int i = 1; i <= n; ++i ) {
		f[i] = 0;
	}

	int k = 0;

	while ( nodes.size() ) {
		if ( !f[nodes.top()] ) {
			reverseDfs(nodes.top(), ++k);
		}
		nodes.pop();	
	}

	cout<<k<<'\n';
	
	for ( int i = 1; i <= k; ++i ) {
		for ( auto x:ctc[i] ) {
			cout<<x<<" ";
		}
		cout<<'\n';
	}
}