Pagini recente » Cod sursa (job #1549058) | Cod sursa (job #2731520) | Cod sursa (job #1233643) | Cod sursa (job #1640095) | Cod sursa (job #1340976)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int MAXN = 100010;
vector <int> Graf[MAXN], GrafT[MAXN];
vector < vector <int> > CTC;
int St[MAXN];
bool Viz[MAXN];
void TopSort (const int &node)
{
Viz[node] = 1;
vector <int> :: iterator it;
for (it = GrafT[node].begin (); it != GrafT[node].end (); ++ it)
if (!Viz[*it])
TopSort (*it);
St[++ St[0]] = node;
}
vector <int> now;
void DFS (const int &node)
{
now.push_back (node);
Viz[node] = 1;
vector <int> :: iterator it;
for (it = Graf[node].begin (); it != Graf[node].end (); ++ it)
if (!Viz[*it])
DFS (*it);
}
int main()
{
int N, M, a, b;
int i, j;
in >> N >> M;
for (i = 1; i <= M; i ++){
in >> a >> b;
Graf[a].push_back (b);
GrafT[b].push_back (a);
}
for (i = 1; i <= N; i ++)
if (!Viz[i])
TopSort (i);
for (i = 1; i <= N; i ++)
Viz[i] = 0;
for (i = N; i; i --)
if (!Viz[St[i]]){
now.clear ();
DFS (St[i]);
CTC.push_back (now);
}
int X = CTC.size ();
out << X << "\n";
for (i = 0; i < X; i ++, out << "\n")
for (j = 0; j < CTC[i].size (); j ++)
out << CTC[i][j] << " ";
return 0;
}