Pagini recente » Cod sursa (job #2544510) | Cod sursa (job #1843317) | Cod sursa (job #843662) | Rating Vlad Camarasoiu (vladcamarasoiu) | Cod sursa (job #2668704)
#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 (unsigned int i=0; i<adj[nod].size(); i++)
{
if (!vizitat[adj[nod][i]])
dfs(adj[nod][i]);}
stiva.push(nod);
}
void dfst(int nod)
{
conex[nrconex].push_back(nod);
vizitat[nod]=2;
for (unsigned int i=0; i<trans[nod].size(); i++)
{
if (vizitat[trans[nod][i]] ==1)
dfst(trans[nod][i]);
}
}
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()==0)
{
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<int(conex[i].size()); j++)
{
g<<conex[i][j]<<" ";
}
g<<endl;
}
}