Pagini recente » Cod sursa (job #1531493) | Cod sursa (job #294851) | Cod sursa (job #1925265) | Cod sursa (job #1888654) | Cod sursa (job #2666569)
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, viz[100001], comp;
vector <int> l1[100001],l2[100001],rez[100001];
stack <int> stiva;
void DFS(int node)
{
viz[node]=1;
for(int i=0; i<l1[node].size(); i++)
{
if(viz[l1[node][i]]==0)
DFS(l1[node][i]);
}
stiva.push(node);
}
void DFS2(int node)
{
viz[node]=1;
rez[comp].push_back(node);
for(int i=0; i<l2[node].size(); i++)
if (viz[l2[node][i]]==0)
DFS2(l2[node][i]);
}
int main()
{
int i,j,k;
fin>>N>>M;
for(i=0; i<M; i++)
{
fin>>j>>k;
l1[j].push_back(k);
l2[k].push_back(j);
}
for(i=1; i<=N; i++)
{
if(viz[i]==0)
DFS(i);
}
for (i=1; i<=N; i++)
viz[i]=0;
while(!stiva.empty())
{
int nod=stiva.top();
if(viz[nod]==0)
{
comp++;
DFS2(nod);
}
stiva.pop();
}
fout<<comp<<endl;
for(i=1; i<=comp; i++)
{
for(j=0; j<rez[i].size(); j++)
fout<<rez[i][j]<< " ";
fout<<endl;
}
return 0;
}