Cod sursa(job #2923792)

Utilizator WladDalwMvladutu cristian vlad WladDalwM Data 19 septembrie 2022 10:45:00
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> e[100005];

int d[100005];

bool vis[100005];
bool f[100005];

int stk[100005];

int k(0);

vector<vector<int>> comp;

void dfs(int a, int l)
{
		vis[a] = true;
		d[a] = l;
		stk[++k] = a;
		f[a] = true;
		for(auto x:e[a])
		{
				if(vis[x] == false)
				{
					dfs(x, l + 1);
				}
		}
		for(auto x:e[a])
		{
				if(vis[x] == true)
				{
					if(f[x] == true)
							d[a] = min(d[a], d[x]);
				}
		}
		if(d[a] == l)
		{
				vector<int> c;
				while(stk[k] != a)
				{
					f[stk[k]] = false;
					c.push_back(stk[k]);
					k--;
				}
				f[stk[k]] = false;
				c.push_back(stk[k]);
				k--;
				comp.push_back(c);
		}
}


int main()
{
		ifstream cin("ctc.in");
		ofstream cout("ctc.out");
		int n,	m;
		cin >> n >> m;
		for(int i(1); i <= m; ++i)
		{
				int a, b;
				cin >> a >> b;
				a[e].push_back(b);
		}
		for(int i(1); i <= n; ++i)
		{
				if(vis[i] == 0)
					dfs(i, 1);
		}
		cout << comp.size() << '\n';
		for(auto c:comp)
		{
				for(auto x:c)
				{
					cout << x << " ";
				}
				cout << '\n';
		}
		return 0;
}