Cod sursa(job #3370374)

Utilizator lvncarsteaCarstea Lavinia Ionela Gabriela lvncarstea Data 25 octombrie 2026 19:58:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
 #include <bits/stdc++.h>
 using namespace std;

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

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

void read()
{
	in>>noduri>>muchii;
	graf.resize(noduri+1);
	graftr.resize(noduri+1);
	viz.resize(noduri+1);
	final.resize(noduri+1);
	for(int i=0;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])
		{
			dfs(nod_vecin);
		}
	}
	st.push_back(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=0;i<noduri;i++)
	{
		if(!viz[i])
			dfs1(i);
	}
	for(int cnt=0;cnt<st.size();cnt++)
	{
		x=st.pop();  
		if(!final[x])
		{
			nr++;
			dfs2(x);
		}
	}
	out<<nr<<'\n';
	for(int i=0;i<ctc.size();i++)
		{
		for(int nod : ctc[i])
			out<<nod<<" ";
		out<<'\n';
		}
 }