Cod sursa(job #3375087)

Utilizator lvncarsteaCarstea Lavinia Ionela Gabriela lvncarstea Data 10 noiembrie 2026 12:07:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
 using namespace std;

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

 int noduri, muchii, x, y, nr;
 const int nmax=100001;
 vector<int> graf[nmax], graftr[nmax];
 int d[nmax], f[nmax];
 stack<int> st;
 int viz[nmax], final[nmax];
 vector<int> ctc[nmax];

void read()
{
	in>>noduri>>muchii;
	for(int i=1;i<=muchii;i++)
	{
		in>>x>>y;
		graf[x].push_back(y);
		graftr[y].push_back(x);
	}
}

void dfs1(int nod)
{
	viz[nod]=1;
	for(auto nod_vecin : graf[nod])
	{
		if(!viz[nod_vecin])
		{
			dfs1(nod_vecin);
		}
	}
	st.push(nod);
}

void dfs2(int nod)
{
	final[nod]=1;
	ctc[nr].push_back(nod);
	for(int elem : graftr[nod])
	{
		if(!final[elem])
			dfs2(elem);
	}
}

 int main()
 {
	read();
	for(int i=1;i<=noduri;i++)
	{
		if(!viz[i])
			dfs1(i);
	}
	while(!st.empty())
	{
		x=st.top();  
		st.pop();

		if(!final[x])
		{
			nr++;
			dfs2(x);
		}
	}
	out<<nr<<'\n';
	for(int i=1;i<=nr;i++)
		{
		for(int nod : ctc[i])
			out<<nod<<" ";
		out<<'\n';
		}
	return 0;
 }