Pagini recente » Cod sursa (job #1457112) | Cod sursa (job #1329025) | Cod sursa (job #1332742) | Cod sursa (job #1334056) | Cod sursa (job #881779)
Cod sursa(job #881779)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int MAXN = 100010;
stack <int> S;
vector <int> Graf[MAXN];
vector < vector <int> > Sol;
bool Viz[MAXN];
int low[MAXN], index[MAXN];
int now;
void tarjan (int nod)
{
int x;
vector <int> :: iterator it;
++ now;
index[nod] = now;
low[nod] = now;
S.push (nod);
Viz[nod] = 1;
for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it){
if (index[*it] == -1){
tarjan (*it);
low[nod] = min (low[nod], low[*it]);
}
else
if (Viz[*it])
low[nod] = min (low[nod], index[*it]);
}
if (low[nod] == index[nod]){
vector <int> CTC;
do{
CTC.push_back (x = S.top ());
Viz[x] = 0;
S.pop ();
}while (x != nod);
Sol.push_back (CTC);
}
}
int main()
{
int N, M, i, j, a, b;
in >> N >> M;
for (i = 1; i <= N; i ++)
index[i] = -1;
while (M --){
in >> a >> b;
Graf[a].push_back (b);
}
for (i = 1; i <= N; i ++)
if (index[i] == -1)
tarjan (i);
out << Sol.size () << "\n";
for (i = 0; i < Sol.size (); i ++, out << "\n")
for (j = 0; j < Sol[i].size (); j ++)
out << Sol[i][j] << " ";
return 0;
}