Pagini recente » Cod sursa (job #2036510) | Cod sursa (job #715692) | Cod sursa (job #2645956) | Cod sursa (job #3260034) | Cod sursa (job #651358)
Cod sursa(job #651358)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define lim 100001
#define pb push_back
using namespace std;
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
int nr,n,m,x,y,j,niv;
int stv[lim],Niv[lim],nivmin[lim];
char viz[lim],Viz[lim];
vector <vector <int> > S ;
vector <int> v[100001];
inline int min(int a,int b){
if(a<b)return a;
return b;
}
void stiva(int t){
vector <int> sol;
do{
sol.pb(stv[j]);
Viz[stv[j]]=0;
j--;
}
while(stv[j+1]!=t);
S.pb(sol);
nr++;
}
void dfs(int nod){
niv++;
Viz[nod]=viz[nod]=1;
Niv[nod]=nivmin[nod]=niv;
for(int i=0;i<v[nod].size();i++){
if(!viz[v[nod][i]])
{
stv[++j]=v[nod][i];
dfs(v[nod][i]);
nivmin[nod]=min(nivmin[nod],nivmin[v[nod][i]]);
}else
if(Viz[v[nod][i]]){
nivmin[nod]=min(nivmin[nod],nivmin[v[nod][i]]);
}
}
if(Niv[nod]==nivmin[nod]){
stiva(nod);
}
}
int main(){
fscanf(f,"%d%d",&n,&m);
for(int i=1;i<=m;++i){
fscanf(f,"%d%d",&x,&y);
v[x].pb(y);
}
for(int i=1;i<=n;i++){
if(viz[i]==0){
stv[++j]=i;
dfs(i);
}
}
fprintf(g,"%d\n",nr);
for(int i=0;i<nr;++i){
for(int j=0;j<S[i].size();j++){
fprintf(g,"%d ",S[i][j]);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}