Pagini recente » Cod sursa (job #378164) | Cod sursa (job #354962) | Cod sursa (job #2216035) | Cod sursa (job #1236891) | Cod sursa (job #1038173)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
typedef vector<vector<int> > GRAPH;
#define DMAX 100005
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void Read();
void DFS(int node);
void DFS2(int node);
int n, m, ct;
GRAPH G, GT;
vector<bool> viz;
vector<int> ord;
vector<vector<int> > Sol;
int main()
{
Read();
for (int i = 1; i <= n; ++i)
if ( !viz[i] ) DFS(i);
viz.assign(viz.size()+1, 0);
for (int i = n; i > 0; --i)
if ( !viz[ord[i]] )
{
ct++;
DFS2(ord[i]);
}
fout << ct << '\n';
for (int i = 1; i <= ct; ++i)
{
for (unsigned int it = 0; it < Sol[i].size(); ++it)
fout << Sol[i][it] << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void DFS(int node)
{
viz[node] = true;
vector<int>::iterator it;
for (it = G[node].begin(); it != G[node].end(); ++it)
if ( !viz[*it] ) DFS(*it);
ord.push_back(node);
}
void DFS2(int node)
{
viz[node] = true;
Sol[ct].push_back(node);
vector<int>::iterator it;
for (it = GT[node].begin(); it != GT[node].end(); ++it)
if ( !viz[*it] ) DFS2(*it);
}
void Read()
{
fin >> n >> m;
G.resize(n+1), GT.resize(n+1), viz.resize(n+1);
Sol.resize(n+1);
ord.push_back(0);
int x, y;
for (int i = 0; i < m; ++i)
{
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}