Pagini recente » Cod sursa (job #1669623) | Cod sursa (job #940315) | Cod sursa (job #2626593) | Cod sursa (job #2197505) | Cod sursa (job #2668470)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,x,y,i,j;
stack<int> stiva;
vector <int> adj[100001], trans[100001], conex[100001];
int vizitat[100001], nrconex;
void dfs(int nod) {
vizitat[nod]=1;
for (int i=0; i<int(adj[nod].size()); i++)
{int vecin=adj[nod][i];
if (!vizitat[vecin])
dfs(vecin);}
stiva.push(nod);
}
void dfst(int nod)
{
vizitat[nod]=2;
conex[nrconex].push_back(nod);
for (i=0; i<trans[nod].size(); i++)
{
int x=trans[nod][i];
if (vizitat[x] ==1)
dfst(x);
}
}
int main()
{
f>>N>>M;
for (i=1; i<=M; i++)
{
f>>x>>y;
adj[x].push_back(y);
trans[y].push_back(x);
}
for (i=1; i<=N; i++)
{if (vizitat[i]==0)
dfs(i);}
while (!stiva.empty())
{
int varf=stiva.top();
if (vizitat[varf] == 1)
{
nrconex++;
dfst(varf);
}
stiva.pop();
}
g<<nrconex<<endl;
for (i=1; i<=nrconex; i++)
{
for (j=0; j<conex[i].size(); j++)
{
g<<conex[i][j]<<" ";
}
g<<endl;
}
}