Cod sursa(job #2971533)

Utilizator NiffSniffCojocaru Calin Marcu NiffSniff Data 27 ianuarie 2023 15:53:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 100000;
string file = "matroid";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
vector <int> succesori[N+1], predecesori[N+1], sir;
vector <vector <int> > conexe;
bitset<N + 1>viz;
void dfs(int x)
{
	viz[x] = 1;
	for (int y : succesori[x])
	{
		if (!viz[y])
		{
			dfs(y);
		}
	}
	sir.push_back(x);
}

void dfs_t(int x)
{
	viz[x] = 0;
	conexe[conexe.size() - 1].push_back(x);
	for (int y : predecesori[x])
	{
		if (viz[y])
		{
			dfs_t(y);
		}
	}
}
int main()
{
	int n,m,x,y;
	cin >> n >> m;
	while (m)
	{
		m--;
		cin >> x >> y;
		succesori[x].push_back(y);
		predecesori[y].push_back(x);
	}
	int ok = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			dfs(i);
		}
		if (predecesori[i].size() == 0)
		{
			if (ok)
			{
				cout << 0;
				return 0;
			}
			ok = i;
		}
	}
	if (ok)
	{
		cout << ok;
		return 0;
	}
	reverse(sir.begin(), sir.end());
	for (int x : sir)
	{
		if (viz[x])
		{
			dfs_t(x);
		}
	}
	cout << conexe[0].size() << '\n';
	for (int x : conexe[0])
	{
		cout << x << '\n';
	}
}