Pagini recente » Cod sursa (job #1266576) | Cod sursa (job #118505) | Cod sursa (job #2653582) | Cod sursa (job #467132) | Cod sursa (job #383226)
Cod sursa(job #383226)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define nmax 100005
#define mmax 200005
#define pb push_back
using namespace std;
int n, m, t, nc, timp [nmax];
vector <pair <int, int> > vt (nmax);
vector <int> G [nmax];
vector <int> Gt [nmax];
vector <int> C [nmax];
bool viz [nmax];
void scan ()
{
int i, a, b;
scanf ("%d%d", &n, &m);
for (i=1; i <= m; ++i)
{
scanf ("%d%d", &a, &b);
G [a].pb (b);
Gt [b].pb (a);
}
}
void init ()
{
int i;
for (i=1; i <= n; ++i)
{
vt.pb (make_pair (timp [i], i));
// fprintf(stderr, "%d %d\n", (vt.end ()-1)->first, (vt.end ()-1)->second);
}
}
void DFS1 (int nod)
{
vector <int> :: iterator it;
++t;
viz [nod]=true;
for (it=G [nod].begin (); it != G [nod].end () ; ++it)
if (viz [*it] == false)
DFS1 (*it);
timp [nod] = ++t;
}
void DFS2 (int nod)
{
vector <int> :: iterator it;
C [nc].pb (nod);
viz [nod]=true;
for (it=Gt [nod].begin (); it != Gt [nod].end (); ++it)
if (viz [*it] == false)
DFS2 (*it);
}
void ctc ()
{
int i;
vector <pair <int, int> > :: iterator it;
for (i=1; i <= n; ++i)
if (viz [i] == false)
DFS1 (i);
memset (viz, 0, sizeof (viz));
init ();
sort (vt.begin (), vt.end ());
for (it=vt.end (); it != vt.begin (); --it)
{
//fprintf(stderr, "%d %d\n", vt [i].first, vt [i].second);
if (viz [it->second] == false)
{
DFS2 (it->second);
++nc;
}
}
--nc;
}
void print ()
{
int i;
vector <int> :: iterator it;
printf ("%d\n", nc);
for (i=1; i <= nc; ++i)
{
for (it=C [i].begin (); it != C [i].end (); ++it)
printf ("%d ", *it);
printf ("\n");
}
}
int main ()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
scan ();
ctc ();
print ();
return 0;
}