Pagini recente » Cod sursa (job #487427) | Cod sursa (job #1745871) | Cod sursa (job #1758372) | Cod sursa (job #1721090) | Cod sursa (job #395551)
Cod sursa(job #395551)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define DIM 100005
#define pb push_back
struct nod
{
int x;
nod *next;
};
struct Stack
{
int u, v;
} stack[DIM];
nod *G[DIM];
int top,n, m, v[DIM], lowpoint[DIM], depth[DIM], adancime, Count;
vector <Stack> comp[DIM];
void addMuchie(int i, int j)
{
nod *p = new nod;
p->x = j;
p->next = G[i];
G[i] = p;
}
void afis()
{
for (int i = 1; i <= n; ++i)
{
printf ("%d:", i);
for (nod *p = G[i]; p; p = p->next)
printf ("%d ", p->x);
printf ("\n");
}
}
void update(int x, int y)
{
++Count;
Stack s;
do
{
s.u = stack[top].u;
s.v = stack[top].v;
--top;
comp[++Count].pb(s);
}while (x != s.u || y != s.v);
}
void DFS(int i)
{
v[i] = 1;
// printf ("%d \n", i);
lowpoint[i] = depth[i] = ++adancime;
for (nod *p = G[i]; p; p = p->next)
if (!v[p->x])
{
++top;
stack[top].u = i;
stack[top].v = p->x;
DFS(p->x);
if (lowpoint[i] >= depth[i])
update(i, p->x);
lowpoint[i] = min(lowpoint[i], lowpoint[p->x]);
}
else
lowpoint[i] = min(lowpoint[i], depth[p->x]);
}
int main()
{
FILE *f = fopen("biconex.in", "r");
fscanf(f, "%d%d", &n, &m);
for (int x, y;m; --m)
{
fscanf(f, "%d%d", &x, &y);
addMuchie(x, y);
addMuchie(y, x);
}
fclose(f);
for (int i = 1; i <= n; ++i)
if (!v[i])
adancime = 0, DFS(i);
// afis();
f = fopen("biconex.out", "w");
fprintf (f, "%d ", Count);
fclose(f);
return 0;
}