Pagini recente » Cod sursa (job #1333036) | Cod sursa (job #866545) | Cod sursa (job #1046240) | Cod sursa (job #2226478) | Cod sursa (job #3216134)
#include <bits/stdc++.h>
using namespace std;
const int Lim = 1e6;
int p = Lim-1;
char buf[Lim];
void next()
{
if(p==Lim)
{fread(buf,1,Lim,stdin);
p = 0;}
else p++;
}
void get(int &x)
{
while(!isdigit(buf[p]))next();
x = 0;
for(;isdigit(buf[p]);next())
{
x*=10;
x += buf[p] - '0';
}
}
#define eb emplace_back
#define pb push_back
#define Inf 0x3f3f3f3f
using vi = vector<int>;
using vvi = vector<vi>;
const int Nmax = 1e5+10;
vvi G;
int n,m;
int nrcomp=0;
vvi compctc;
int incomp[Nmax],disc[Nmax],low[Nmax];
stack<int> stk;
bool instk[Nmax];
int t = 0;
void dfs(int nod)
{
t++;
disc[nod] = t;
low[nod] = t;
stk.push(nod);
instk[nod] = true;
for(auto c:G[nod])
{
//cout<<"merg: "<<nod<<" "<<c<<endl;
if(disc[c]==Inf)
{
dfs(c);
low[nod] = min(low[nod],low[c]);
}
else if(instk[c]) low[nod] = min(low[nod],disc[c]);
}
if(low[nod]==disc[nod])
{
nrcomp++;
vi aux;
compctc.pb(aux);
int now=-1;
while(now!=nod&&stk.size()>0)
{
now = stk.top();
incomp[now] = nrcomp;
compctc[nrcomp].eb(now);
instk[now] = false;
stk.pop();
}
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
get(n);
get(m);
G = vvi(n+1);
vi aux;
compctc.pb(aux);
for(int i=1;i<=n;i++)
disc[i] = low[i] = Inf;
for(int i=1;i<=m;i++)
{
int x,y;
get(x);
get(y);
G[x].eb(y);
}
for(int i=1;i<=n;i++)
if(disc[i]==Inf)
{
t = 0;
dfs(i);
}
printf("%d\n",nrcomp);
for(int i=1;i<=nrcomp;i++)
{for(auto c:compctc[i])
printf("%d ",c);
printf("\n");
}
return 0;
}