Pagini recente » Cod sursa (job #353645) | Monitorul de evaluare | Rating Raissa Sandor (Raissa14) | Cod sursa (job #200129) | Cod sursa (job #371010)
Cod sursa(job #371010)
#include <cstdio>
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];
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 parcurgere(int varf, nod * GRAF[], int v[]){
v[varf]=1;
for(nod *p = GRAF[varf]; p ; p = p -> next)
if(!v[p->info])
parcurgere(p->info, GRAF, v);
}
void plus_minus(){
for(int i =1 ; i<=n;i++)
if(v[i]==0){
for(int j=1;j<=n;j++)
plus[j]=minus[j]=0;
parcurgere(i,G,plus);
parcurgere(i,GT,minus);
nrc++;
for(int j=1;j<=n;j++)
if(plus[j]+minus[j]==2)
v[j] = nrc;
}
}
int main(){
read();
plus_minus();
write();
return 0;
}