Pagini recente » Cod sursa (job #523588) | Cod sursa (job #1827351) | Cod sursa (job #858309) | Cod sursa (job #611707) | Cod sursa (job #2668360)
#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=0;
void dfs(int nod) {
vizitat[nod]=true;
for (auto vecin: adj[nod])
{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++)
{
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);
}
f.close();
for (i=1; i<=N; i++)
if (!vizitat[i])
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<conex[i].size(); j++)
{
g<<conex[i][j]<<" ";
}
g<<endl;
}
}