Pagini recente » Cod sursa (job #1476101) | Cod sursa (job #575584) | Cod sursa (job #2208801) | Cod sursa (job #612177) | Cod sursa (job #611578)
Cod sursa(job #611578)
#include<cstdio>
#include<vector>
#include<stack>
#define stiva stack<int>
#define minim(a,b) a<b?a:b
using namespace std;
vector<int>V[100010],componenta;
vector<vector<int> >SOL;
stiva S;
void read(),solve(),tarjan(int);
int n,m,a,i,b,viz[100010],ind[100010],curr=1,lowlink[100010],aux;
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;--m)
{
scanf("%d%d",&a,&b);
V[a].push_back(b);
}
}
void solve()
{
for(i=1;i<=n;i++)
if(!ind[i])tarjan(i);
printf("%d\n",SOL.size());
for(unsigned i=0;i<SOL.size();i++)
{
for(vector<int>::iterator it=SOL[i].begin();it!=SOL[i].end();it++)
printf("%d ",*it);
printf("\n");
}
}
void tarjan(int X)
{
ind[X]=curr;
lowlink[X]=curr;
++curr;
S.push(X);viz[X]=1;
for(vector<int>::iterator it=V[X].begin();it!=V[X].end();it++)
{
if(!ind[*it]){tarjan(*it);lowlink[X]=minim(lowlink[X],lowlink[*it]);}
else if(viz[*it])lowlink[X]=minim(lowlink[X],lowlink[*it]);
}
if(lowlink[X]==ind[X])
{
componenta.resize(0);
int aux;
do
{
aux=S.top();
componenta.push_back(aux);
viz[aux]=0;
S.pop();
}while(aux!=X);
SOL.push_back(componenta);
}
}