Pagini recente » Cod sursa (job #970630) | Cod sursa (job #1385563) | Cod sursa (job #1647967) | Cod sursa (job #1335112) | Cod sursa (job #2929537)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, nrComponente, x, y;
bool vizitate[100001], inStiva[100001];
stack <int> stiva;
vector <int> adiacenta[100001], componenteConexe[100001], rev[100001];
void build(int nod)
{
inStiva[nod] = true;
for(int urmator : adiacenta[nod])
{
if(inStiva[urmator])
continue;
build(urmator);
}
stiva.push(nod);
}
void dfs(int nod)
{
vizitate[nod] = true;
componenteConexe[nrComponente].push_back(nod);
for(int urmator : rev[nod])
{
if(vizitate[urmator])
continue;
dfs(urmator);
}
}
int main()
{
f>>N>>M;
for(int i = 0; i < M; i++)
{
f>>x>>y;
adiacenta[x].push_back(y);
rev[y].push_back(x);
}
for(int i = 0; i < N; ++i)
{
if(inStiva[i])
continue;
build(i);
}
while(stiva.size())
{
int curent = stiva.top();
stiva.pop();
if(vizitate[curent])
continue;
++nrComponente;
dfs(curent);
}
g<<nrComponente<<'\n';
for(int i = 0; i < nrComponente; ++i)
{
for(int nod : componenteConexe[i])
g<<nod<<' ';
g<<'\n';
}
g.close();
f.close();
return 0;
}