Cod sursa(job #3370448)

Utilizator lvncarsteaCarstea Lavinia Ionela Gabriela lvncarstea Data 26 octombrie 2026 12:13:14
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
 #include<bits/stdc++.h>

 using namespace std;
 ifstream in("ctc.in");
 ofstream out("ctc.out");

const int nmax = 100001;

vector<int> graf[nmax];
vector<int> graftr[nmax];
vector<int> ctc[nmax];

int plus[nmax], minus[nmax];
int elm[nmax];
int n, m, x, y, ult=1, nr=0;

void dfsp(int nod)
{
	plus[nod]=1;
	for(auto nod_vecin : graf[nod])
		if(!plus(nod_vecin) && !eml[nod_vecin] )
			dfsp(nod_vecin);
}

void dfsm(int nod)
{
	minus[nod]=1;
	for(auto nod_vecin :graftr[nod])
		if(!minus(nod_vecin) && !eml[nod_vecin])
			dfsm(nod_vecin);
}

int v()
{
	ult=-1;
	for(int i=1;i<=n;i++)
	{
		
		if(minus[i] * plus[i])
		{
			ctc[nr].push_back(i);
			eml[i]=1;
		}
		else
		{
			minus[i]=0;
			plus[i]=0;
			if(!elm[i])
				ult=i;
		}
	}
	return ult;
}

int main()
{
	in>>n>>m;
	for(int i=0;i<m;i++)
	{
		in>>x>>y;
		graf[x].push_back(y);
		graftr[y].push_back(x);
	}

	while(graf.size())
	{
		nr++;

		dfsp(ult);
		dfsm(ult);
		ult=v();
		
		if(ult == -1)
			break;
	}
	
	out<<nr;
	for(int i=0;i<nr;i++)
		for(int nod : ctc[i])
			out<<nod<<" ";
}