Cod sursa(job #2380371)

Utilizator petrea1551Petrea Calin petrea1551 Data 14 martie 2019 20:50:01
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> v[100001], vt[100001];
vector<vector<int>> scc;
bool viz[100001];
int n, m, k;
stack<int> st;
set<int> ms;

void dfs(int nod)
{
	viz[nod] = 1;
	for (int i = 0; i < v[nod].size(); i++)
		if (!viz[v[nod][i]])
			dfs(v[nod][i]);
	st.push(nod);
}

void dfst(int nod)
{
	viz[nod] = 1;
	ms.insert(nod);
	scc[k].push_back(nod);
	for (int i = 0; i < vt[nod].size(); i++)
		if (!viz[vt[nod][i]])
			dfst(vt[nod][i]);
}

int main()
{
	ifstream cin("ctc.in");
	ofstream cout("ctc.out");
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		vt[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			dfs(i);
	k = 0;
	for (int i = 1; i <= n; i++)
		viz[i] = 0;
	vector<int> vid;
	scc.push_back(vid);
	while (!st.empty())
	{
		int temp = st.top();
		st.pop();
		if (ms.find(temp) == ms.end())
		{
			vector<int> vid;
			scc.push_back(vid);
			k++;
			dfst(temp);
		}
	}
	cout << k << endl;
	for (int i = 1; i <= k; i++)
	{
		for (int j = 0; j < scc[i].size(); j++)
			cout << scc[i][j] << ' ';
		cout << '\n';
	}
	return 0;
}