Pagini recente » Cod sursa (job #2786810) | Cod sursa (job #3038379) | Cod sursa (job #3280243) | Cod sursa (job #458988) | Cod sursa (job #1494245)
#include <vector>
#include <stack>
#include <cstdio>
#define nmax 100010
#define pb push_back
#define min(a,b) ( (a)<(b)? (a) : (b) )
using namespace std;
int n,m1,idx[nmax],lowlink[nmax],index,ins[nmax];
vector<int> m[nmax],ctc;
vector< vector<int> > sol;
stack<int> s;
void tarjan(int n)
{
index++;
idx[n]=index; lowlink[n]=index;
s.push(n); ins[n]=1;
vector<int>::iterator it;
for(it=m[n].begin();it!=m[n].end();it++)
if(!idx[*it]) { tarjan(*it); lowlink[n]=min(lowlink[n],lowlink[*it]);}
else if(ins[*it]) lowlink[n]=min(lowlink[n],idx[*it]);
if(lowlink[n]==idx[n])
{
ctc.clear();
int nod;
do
{
nod=s.top(); s.pop();
ctc.pb(nod); ins[nod]=0;
} while(nod!=n);
sol.pb(ctc);
}
}
int main()
{
int n1,n2;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m1);
for(;m1;m1--)
{
scanf("%d%d",&n1,&n2);
m[n1].pb(n2);
}
for(int i=1;i<=n;i++)
if(!idx[i]) tarjan(i);
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++)
{
for(int j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}
/*void tarjan(int v)
{
index++;
idx[v]=index; lowlink[v]=index;
s.push(v); in_stack[v]=1;
vector<int>::const_iterator it;
for(it=vert[v].begin();it!=vert[v].end();it++)
if(idx[*it]==0) { tarjan(*it); lowlink[v]=minim(lowlink[v],lowlink[*it]); }
else if(in_stack[*it]) lowlink[v]=minim(lowlink[v],lowlink[*it]);
if(lowlink[v]==idx[v])
{
ctc.clear();
int node;
do
{
ctc.push_back(node=s.top()); s.pop(); in_stack[node]=0;
}while(node!=v);
sol.push_back(ctc);
}
}
int main()
{
int n1,n2,j;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;m--)
{
scanf("%d%d",&n1,&n2);
vert[n1].push_back(n2);
}
for(int i2=1;i2<=n;i2++)
if(idx[i2]==0) tarjan(i2);
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++)
{
for(j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}*/