Cod sursa(job #2711956)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 24 februarie 2021 22:06:24
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> g[100001], gr[100001], com[100001];

bitset <100001> marked;

int ord[100001];
int N, M, nr;

void dfs1(int v){
	marked[v] = 1;
	for(int to : g[v])
		if(!marked[to])
			dfs1(to);

	ord[++ord[0]] = v;
}

void dfs2(int v){
	marked[v] = 1;
	com[nr].emplace_back(v);
	for(int to : gr[v])
		if(!marked[to])
			dfs2(to);

}

int main(){
	fin >> N >> M;

	while(M--){
		int x, y;
		fin >> x >> y;
		g[x].emplace_back(y);
		gr[y].emplace_back(x);
	}

	for(int i = 1;i <= N;i++)
		if(!marked[i])
			dfs1(i);

	marked.reset();
	for(int i = 1;i <= N;i++){
		int v = ord[N - i + 1];
		if(!marked[v]){
			nr++;
			dfs2(v);
		}
	}

	fout << nr << "\n";
	for(int i = 1;i <= nr;i++, fout << "\n")
		for(int x : com[i])
			fout << x << " ";
}