Pagini recente » Cod sursa (job #551476) | Cod sursa (job #2018507) | Cod sursa (job #2084530) | Cod sursa (job #2068206) | Cod sursa (job #479430)
Cod sursa(job #479430)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
const char iname[] = "ctc.in";
const char oname[] = "ctc.out";
ifstream fin(iname);
ofstream fout(oname);
vector<int> Graph[nmax];
vector<int> InvGraph[nmax];
vector<int> Road[nmax];
int N, M, i, j, Father[nmax], sol, viz[nmax], viz2[nmax], k, x, y, nr;
void DFS1(int nod)
{
viz[nod] = 1;
for(vector<int>::iterator it = Graph[nod].begin(); it != Graph[nod].end(); ++it)
if(!viz[*it])
DFS1(*it);
Father[++k] = nod;
}
void DFS2(int nod)
{
viz[nod] = 0;
for(vector<int>::iterator it = InvGraph[nod].begin(); it != InvGraph[nod].end(); ++it)
if(viz[*it])
DFS2(*it);
Road[sol].push_back(nod);
}
int main()
{
fin >> N >> M;
for(i = 1; i <= M; i ++)
{
fin >> x >> y;
Graph[x].push_back(y);
InvGraph[y].push_back(x);
}
for(i = 1; i <= N; i ++)
if(!viz[i])
DFS1(i);
for(i = N; i >= 1; i --)
if(viz[Father[i]])
{
++ sol;
DFS2(Father[i]);
}
fout << sol << "\n";
for(i = 1; i <= sol; i ++)
{
for(j = 0; j < Road[i].size(); j ++)
fout << Road[i][j] << " ";
fout << "\n";
}
return 0;
}