Pagini recente » Cod sursa (job #2986566) | Cod sursa (job #19962) | Cod sursa (job #2769844) | Cod sursa (job #3126670) | Cod sursa (job #282317)
Cod sursa(job #282317)
using namespace std;
#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>
#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define IN "ctc.in"
#define OUT "ctc.out"
#define N_MAX 1<<17
typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;
int rez(-1),N,M,indx(1);
vector<bool> in_stack(N_MAX);
int ind[N_MAX],lowind[N_MAX],con;
vector<VI> A(N_MAX),C(N_MAX);
stack<int> S;
II void scan()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d %d\n",&N,&M);
int x,y;
FOR(i,1,M)
{
scanf("%d %d\n",&x,&y);
A[x].pb(y);
}
}
II void Tarjan(int nod)
{
in_stack[nod] = true;
ind[nod] = lowind[nod] = indx++;
S.push(nod);
for(int i=0;i<(int)A[nod].sz();++i)
{
int fiu = A[nod][i];
if(ind[fiu] && !in_stack[fiu])
continue;
if(!ind[fiu])
Tarjan(fiu);
lowind[nod] = min(lowind[nod],lowind[fiu]);
}
if(ind[nod] == lowind[nod])
{
++rez;
for(int fiu = 0;fiu != nod;C[rez].pb(fiu = S.top() ),S.pop(),in_stack[fiu] = false);
}
}
II void solve()
{
FOR(i,1,N)
if(!ind[i])
Tarjan(i);
printf("%d\n",rez+1);
FOR(i,0,rez)
{
for(int j=0;j<(int)C[i].sz();++j)
printf("%d ",C[i][j]);
printf("\n");
}
}
int main()
{
scan();
solve();
return 0;
}