Pagini recente » Cod sursa (job #2632927) | Cod sursa (job #1035341) | Cod sursa (job #3226924) | Cod sursa (job #25731) | Cod sursa (job #371014)
Cod sursa(job #371014)
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 100010
struct nod{
int info;
nod * next;
};
nod * G[MAX], * GT[MAX];
int v[MAX], n, nrc, plus[MAX], minus[MAX],coada[MAX];
void read(){
freopen("ctc.in","r",stdin);
int m , i , j;
nod * p;
scanf("%d%d", &n , &m);
for(i = 1;i<=n;i++)
G[i] = GT[i] = NULL;
for( ; m ;--m){
scanf("%d%d", &i ,&j);
p= new nod ; p->info = j; p->next = G[i]; G[i] = p;
p= new nod ; p->info = i; p->next = GT[j]; GT[j] = p;
}
}
void write(){
freopen("ctc.out","w", stdout);
printf("%d\n", nrc);
for(int i=1;i<=nrc;i++){
for(int j=1;j<=n;j++)
if(v[j]==i)
printf("%d ", j);
printf("\n");
}
}
void dfs(int varf, nod * GRAF[], int v[]){
v[varf]=1;
for(nod *p = GRAF[varf]; p ; p = p -> next)
if(!v[p->info])
dfs(p->info, GRAF, v);
}
void bfs(int start, nod * GRAF[], int v[]){
int st=1, dr=1, k,kk;
coada[dr]=start; v[start] = 1;
while(st<=dr){
k = coada[st++];
for(nod *p = GRAF[k]; p ; p = p -> next)
if(!v[kk = p->info]){
v[kk] =1;
coada[++dr] = kk;
}
}
}
void plus_minus(){
for(int i =1 ; i<=n;i++)
if(v[i]==0){
memset(plus,0,sizeof(plus));
memset(minus,0,sizeof(minus));
bfs(i,G,plus);
bfs(i,GT,minus);
nrc++;
for(int j=1;j<=n;j++)
if(plus[j]+minus[j]==2)
v[j] = nrc,G[j]=GT[j]=NULL;
}
}
int main(){
read();
plus_minus();
write();
return 0;
}