Pagini recente » Cod sursa (job #149) | Cod sursa (job #3206699) | Cod sursa (job #2931957) | Cod sursa (job #2951999) | Cod sursa (job #769273)
Cod sursa(job #769273)
#include<stdio.h>
#include<stdlib.h>
#define SIZE 100001
struct list{ int v; struct list *next;};
typedef struct list list;
FILE *file;
int root[SIZE], level[SIZE], reach[SIZE], stack[200002][2], top, N, nrComponents;
char used[SIZE], inList[SIZE], sw;
list *G[SIZE], *result[SIZE];
void DF(int node)
{
list *p;
used[node] = 1;
reach[node] = level[node];
for(p = G[node]; p; p = p->next)
{
if(p->v != root[node] && level[p->v] < level[node])
stack[++top][0] = node,
stack[top][1] = p->v;
if(!used[p->v])
{
level[p->v] = level[node] + 1;
DF(p->v);
if(reach[p->v] < reach[node])
reach[node] = reach[p->v];
else if(reach[p->v] >= level[node])
{
list *aux;
nrComponents++;
if(sw) sw = 0;
else sw = 1;
do
{
if(inList[stack[top][0]] != sw)
{
inList[stack[top][0]] = sw;
aux = malloc(sizeof(list));
aux->v = stack[top][0];
aux->next = result[nrComponents];
result[nrComponents] = aux;
}
if(inList[stack[top][1]] != sw)
{
inList[stack[top][1]] = sw;
aux = malloc(sizeof(list));
aux->v = stack[top][1];
aux->next = result[nrComponents];
result[nrComponents] = aux;
}
top--;
} while(stack[top+1][0] != node || stack[top+1][1] != p->v);
}
}
else
if(p->v != root[node] && reach[node] > level[p->v])
reach[node] = level[p->v];
}
}
int main()
{
int M, a, b, i;
list *p;
file = fopen("biconex.in", "r");
fscanf(file, "%d %d", &N, &M);
for(; M; --M)
{
fscanf(file, "%d %d", &a, &b);
p = malloc(sizeof(list));
p->v = b;
p->next = G[a];
G[a] = p;
p = malloc(sizeof(list));
p->v = a;
p->next = G[b];
G[b] = p;
}
fclose(file);
sw = 1;
for(i = 1; i <= N; ++i)
if(!used[i])
{
level[i] = 1;
DF(i);
}
file = fopen("biconex.out", "w");
fprintf(file, "%d\n", nrComponents);
for(i = 1; i <= nrComponents; ++i)
{
for(p = result[i]; p; p = p->next)
fprintf(file, "%d ", p->v);
fprintf(file, "\n");
}
fclose(file);
return 0;
}