Cod sursa(job #2722458)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 12 martie 2021 20:59:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

vector <int> v[100001];
vector <int> t[100001];

bool viz[100001];
int post[100001];

int k;
vector <int> comp[100001];

void dfs1 (int r)
{
	viz[r] = 1;
	int i;
	for (i = 0; i<v[r].size(); i++)
		if (viz[v[r][i]] == 0)
			dfs1(v[r][i]);
	post[++post[0]] = r;
}

void dfs2 (int r)
{
	viz[r] = 1;
	comp[k].push_back(r);
	int i;
	for (i = 0; i<t[r].size(); i++)
		if (viz[t[r][i]] == 0)
			dfs2(t[r][i]);
}

int main()
{
	int n, m, i, j, x, y;
	fin >> n >> m;
	for (i = 1; i<=m; i++)
	{
		fin >> x >> y;
		v[x].push_back(y);
		t[y].push_back(x);
	}
	for (i = 1; i<=n; i++)
		if (viz[i] == 0)
			dfs1(i);
	for (i = 1; i<=n; i++)
		viz[i] = 0;
	for (i = n; i>=1; i--)
		if (viz[post[i]] == 0)
		{
			k++;
			dfs2(post[i]);
		}
	fout << k << '\n';
	for (i = 1; i<=k; i++, fout << '\n')
		for (j = 0; j<comp[i].size(); j++)
			fout << comp[i][j] << ' ';
	return 0;
}