Pagini recente » Cod sursa (job #769499) | Cod sursa (job #1927960) | Cod sursa (job #2620429) | Cod sursa (job #337062) | Cod sursa (job #2668713)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
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()
{ int N,M,x,y;
f>>N>>M;
for (int i=1; i<=M; i++)
{
f>>x>>y;
adj[x].push_back(y);
trans[y].push_back(x);
}
for (int 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 (int i=1; i<=nrconex; i++)
{
for (int j=0; j<int(conex[i].size()); j++)
{
g<<conex[i][j]<<" ";
}
g<<endl;
}
}