Pagini recente » Cod sursa (job #1184874) | fmi-no-stress-2012/clasament | Cod sursa (job #3159620) | Cod sursa (job #1796272) | Cod sursa (job #767147)
Cod sursa(job #767147)
#include<stdlib.h>
#include<stdio.h>
struct node{
int value;
struct node *next;
} *G[100001], *Gt[100001];
int N, nrComp, visited[100001], stack[100001];
FILE *in, *out;
void df1(int i)
{
struct node *p;
visited[i] = -1;
for(p = G[i]; p; p = p->next)
if(visited[p->value] == 0)
df1(p->value);
stack[++stack[0]] = i;
}
void df2(int i)
{
struct node *p;
visited[i] = nrComp;
for(p = Gt[i]; p; p = p->next)
if(visited[p->value] == -1)
df2(p->value);
}
int main(){
int i, M, a, b;
struct node *p;
in = fopen("ctc.in", "r");
out = fopen("ctc.out", "w");
fscanf(in, "%d %d", &N, &M);
for(; M; --M){
fscanf(in, "%d %d", &a, &b);
p = malloc(sizeof(struct node));
p->value = b;
p->next = G[a];
G[a] = p;
p = malloc(sizeof(struct node));
p->value = a;
p->next = Gt[b];
Gt[b] = p;
}
for(i = 1; i <= N; ++i)
if(!visited[i]){
df1(i);
}
for(nrComp = 0, i = N; i; --i)
if(visited[stack[i]] == -1){
++nrComp;
df2(stack[i]);
}
fprintf(out, "%d\n", nrComp);
for(i = 1; i <= nrComp; ++i)
{
for(a = 1; a <= N; ++a)
if(visited[a] == i)
fprintf(out, "%d ", a);
fprintf(out, "\n");
}
fclose(in);
fclose(out);
return 0;
}