Pagini recente » Istoria paginii runda/cerculdeinfo-lectia9-cuplaj_flux/clasament | Cod sursa (job #1995829) | Monitorul de evaluare | Cod sursa (job #1234389) | Cod sursa (job #662496)
Cod sursa(job #662496)
#include <cstdio>
#include <vector>
#define NMax 100005
using namespace std;
vector <int> G[NMax], GT[NMax];
int N, SCC[NMax], Found[NMax];
bool Used[NMax];
vector <int> Component[NMax];
void Read ()
{
freopen ("ctc.in", "r", stdin);
int M;
scanf ("%d %d", &N, &M);
for (; M>0; --M)
{
int X, Y;
scanf ("%d %d", &X, &Y);
G[X].push_back (Y);
GT[Y].push_back (X);
}
}
void Print ()
{
freopen ("ctc.out", "w", stdout);
printf ("%d\n", SCC[0]);
for (int i=1; i<=SCC[0]; ++i)
{
for (int j=0; j<Component[i].size (); ++j)
{
printf ("%d ", Component[i][j]);
}
printf ("\n");
}
}
inline void DFP (int X)
{
Used[X]=true;
for (vector <int> :: iterator V=G[X].begin (); V!=G[X].end (); ++V)
{
if (!Used[*V])
{
DFP (*V);
}
}
Found[++Found[0]]=X;
}
inline void DFM (int X, int C)
{
SCC[X]=C;
for (vector <int> :: iterator V=GT[X].begin (); V!=GT[X].end (); ++V)
{
if (!SCC[*V])
{
DFM (*V, C);
}
}
Component[C].push_back (X);
}
void Kosaraju ()
{
for (int i=1; i<=N; ++i)
{
if (!Used[i])
{
DFP (i);
}
}
for (int i=Found[0]; i>0; --i)
{
if (!SCC[Found[i]])
{
++SCC[0];
DFM (Found[i], SCC[0]);
}
}
}
int main()
{
Read ();
Kosaraju ();
Print ();
return 0;
}