Pagini recente » Cod sursa (job #1128875) | Cod sursa (job #1872887) | Cod sursa (job #1991578) | Cod sursa (job #1179592) | Cod sursa (job #579624)
Cod sursa(job #579624)
#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>
#define TR(C, i)\
for(typeof(C.begin()) i = C.begin(); i != C.end(); i++)
#define pb push_back
using namespace std;
int N, M;
const int nmax = 100010;
vector < vector<int> > C;
vector < int > T;
vector < int > G[nmax];
stack <int> S;
int idx[nmax], indecs, lowlink[nmax],In[nmax];
void read()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
int i, a, b;
for(i = 1; i <= M; i++)
{
scanf("%d %d", &a, &b);
G[a].pb( b );
}
memset(idx, -1, sizeof(idx));
}
void solve(int nod)
{
idx[nod] = lowlink[nod] = indecs;
S.push(nod), In[nod] = 1;
indecs++;
TR(G[nod], it)
if(idx[*it] == -1)
solve(*it), lowlink[nod] = min(lowlink[nod], lowlink[*it]);
else if(In[*it]) lowlink[nod] = min(lowlink[nod], lowlink[*it]);
if(lowlink[nod] == idx[nod])
{
int nxt;
T.clear();
do{
nxt = S.top();
In[nxt] = 0;
S.pop();
T.pb( nxt );
} while(nxt != nod);
C.pb( T );
}
}
void OutPut()
{
printf("%d\n", C.size());
TR(C, it)
{
TR((*it), i)
printf("%d ", *i);
printf("\n");
}
}
int main()
{
read();
int i;
for(i = 1; i <= N; i++)
if(idx[i] == -1)
solve(i);
OutPut();
return 0;
}