Pagini recente » Cod sursa (job #2322669) | Cod sursa (job #2241534) | Cod sursa (job #163490) | Cod sursa (job #340402) | Cod sursa (job #2187341)
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
int m,n,cnt;
vector<int> G[NMAX],comp[NMAX];
stack<int> tarjan;
int viz[NMAX],inStack[NMAX],niv[NMAX],best[NMAX];
void insetNod(int nod)
{
comp[cnt].push_back(nod);
inStack[nod]=0;
tarjan.pop();
}
void solve(int nod,int tata)
{
inStack[nod]=viz[nod]=1;
tarjan.push(nod);
niv[nod]=best[nod]=niv[tata]+1;
for(auto fiu:G[nod])
{
if(!viz[fiu])
{
solve(fiu,nod);
best[nod]=min(best[nod],best[fiu]);
}
else if(inStack[fiu])
best[nod]=min(best[nod],best[fiu]);
}
if(best[nod]==niv[nod])
{
cnt++;
while(tarjan.top()!=nod)
{
insetNod(tarjan.top());
}
insetNod(tarjan.top());
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
int nod1,nod2;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&nod1,&nod2);
G[nod1].push_back(nod2);
}
for(int i=1;i<=n;i++)
if(!viz[i])
solve(i,0);
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
for(auto nod:comp[i])
printf("%d ",nod);
printf("\n");
}
return 0;
}