Pagini recente » Monitorul de evaluare | Cod sursa (job #3173784) | Cod sursa (job #1265757) | Cod sursa (job #1121518) | Cod sursa (job #3215735)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAXN 100//005
#define MAXM 200//005
#define ALB 0
#define GRI 1
#define BLK 2
using namespace std;
struct XYZ{
int niv,x;
};
int nod[MAXN];
int nivel[MAXN];
vector <int> graf[MAXN];
vector <int> ans[MAXN];
int fath[MAXN];
int FindFath(int x){
if(fath[x]==x){
return x;
}
fath[x]=FindFath(fath[x]);
return fath[x];
}
void Conect(int x,int y){
int fx,fy;
fx=FindFath(x);
fy=FindFath(y);
if(fx!=fy){
fath[fx]=fy;
}
}
XYZ DFS(int node,int adan){
XYZ aux,r;
r.niv=adan;
r.x=node;
nivel[node]=adan;
nod[node]=GRI;
for(int neigh : graf[node]){
if(nod[neigh]==ALB){
aux=DFS(neigh,adan+1);
if(aux.niv<r.niv){
r=aux;
}
}else{
if(nivel[neigh]<r.niv){
r.niv=nivel[fath[neigh]];
r.x=fath[neigh];
}
}
}
Conect(node,r.x);
nod[node]=BLK;
return r;
}
int main(){
int n,m,i,x,y;
FILE *fin,*fout;
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&x,&y);
graf[x].push_back(y);
}
m=0;
for(i=1;i<=n;i++){
fath[i]=i;
}
for(i=1;i<=n;i++){
if(nod[i]==ALB){
DFS(i,1);
}
}
for(i=1;i<=n;i++){
ans[FindFath(i)].push_back(i);
}
m=0;
for(i=1;i<=n;i++){
if(!ans[i].empty()){
m++;
}
}
fprintf(fout,"%d\n",m);
for(i=1;i<=n;i++){
if(!ans[i].empty()){
for(int aux : ans[i]){
fprintf(fout,"%d ",aux);
}
fprintf(fout,"\n");
}
}
fclose(fin);
fclose(fout);
return 0;
}