Pagini recente » Cod sursa (job #2000113) | Cod sursa (job #1965579) | Clasament repost | Cod sursa (job #1344489) | Cod sursa (job #596538)
Cod sursa(job #596538)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector <int> G[100005];
stack <int> Stack;
vector < vector <int> > CTC;
int N, Index[100005], CIndex, LowestI[100005];
bool InStack[100005];
void Read ()
{
ifstream fin ("ctc.in");
int M, X, Y;
fin >> N >> M;
for (; M>0; --M)
{
fin >> X >> Y;
G[X].push_back (Y);
}
fin.close ();
}
void Type ()
{
ofstream fout ("ctc.out");
unsigned i, j;
fout << CTC.size () << "\n";
for (i=0; i<CTC.size (); ++i)
{
for (j=0; j<CTC[i].size (); ++j)
{
fout << CTC[i][j] << " ";
}
fout << "\n";
}
fout.close ();
}
inline int Min (int a, int b)
{
if (a<b)
{
return a;
}
return b;
}
void DetCTC (int X)
{
int Y;
vector <int> C;
do
{
Y=Stack.top ();
C.push_back (Y);
InStack[Y]=false;
Stack.pop ();
}
while (Y!=X);
CTC.push_back (C);
}
void Tarjan (int X)
{
vector <int> :: iterator V;
Index[X]=CIndex;
LowestI[X]=CIndex;
CIndex++;
Stack.push (X);
InStack[X]=true;
for (V=G[X].begin (); V!=G[X].end (); ++V)
{
if (Index[*V]==-1)
{
Tarjan (*V);
LowestI[X]=Min (LowestI[X], LowestI[*V]);
}
else
{
if (InStack[X]=true)
{
LowestI[X]=Min (LowestI[X], LowestI[*V]);
}
}
}
if (Index[X]==LowestI[X])
{
DetCTC (X);
}
}
int main()
{
int i;
Read ();
for (i=1; i<=N; ++i)
{
Index[i]=-1;
}
for (i=1; i<=N; ++i)
{
if (Index[i]==-1)
{
Tarjan (i);
}
}
Type ();
return 0;
}