Pagini recente » Cod sursa (job #3139876) | Cod sursa (job #1882873) | Cod sursa (job #3216346) | Cod sursa (job #2936191) | Cod sursa (job #2618271)
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <stdlib.h>
#include <limits.h>
#include <vector>
struct Edge
{
int x, y;
};
void dfs(std::vector<int> graph[], int nod, int *disc, int *low, int *time, int *parent, std::stack<Edge> *st, int *nr, std::vector<int> *biconex)
{
disc[nod] = low[nod] = ++(*time);
int children = 0;
for (int k = 0; k < graph[nod].size(); k++)
{
int i = graph[nod][k];
if (disc[i] == -1)
{
parent[i] = nod;
children++;
Edge aux;
aux.x = nod;
aux.y = i;
st->push(aux);
dfs(graph, i, disc, low, time, parent, st, nr, biconex);
low[nod] = std::min(low[nod], low[i]);
if ((disc[nod] == 1 && children > 1) ||
(disc[nod] > 1 && low[i] >= disc[nod]))
{
int flag = 0;
while (st->top().x != nod || st->top().y != i)
{
flag = 1;
biconex[*nr].push_back(st->top().x);
st->pop();
}
if (flag)
biconex[(*nr)++].push_back(st->top().x);
else
{
biconex[*nr].push_back(st->top().x);
biconex[(*nr)++].push_back(st->top().y);
}
st->pop();
}
}
else
{
if (i != parent[nod])
{
low[nod] = std::min(low[nod], disc[i]);
if (disc[i] < disc[nod])
{
Edge aux;
aux.x = nod;
aux.y = i;
st->push(aux);
}
}
}
}
}
int main()
{
FILE *in = fopen("biconex.in", "r");
FILE *out = fopen("biconex.out", "w");
int n, m;
fscanf(in, "%d", &n);
fscanf(in, "%d", &m);
std::vector<int> graph[100000];
int *low = (int *)malloc(n * sizeof(int));
int *disc = (int *)malloc(n * sizeof(int));
int *parent = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
disc[i] = parent[i] = low[i] = -1;
int time = 0;
for (int i = 0; i < m; i++)
{
int nod1, nod2;
fscanf(in, "%d%d", &nod1, &nod2);
nod1--;
nod2--;
graph[nod1].push_back(nod2);
graph[nod2].push_back(nod1);
}
std::stack<Edge> st;
int nr = 0;
std::vector<int> biconex[100000];
dfs(graph, 0, disc, low, &time, parent, &st, &nr, biconex);
if (st.size() == 1)
{
biconex[nr].push_back(st.top().x);
biconex[nr].push_back(st.top().y);
}
else
{
while (!st.empty())
{
biconex[nr].push_back(st.top().x);
st.pop();
}
}
nr++;
fprintf(out, "%d\n", nr);
for (int i = 0; i < nr; i++)
{
for (int j = 0; j < biconex[i].size(); j++)
{
fprintf(out, "%d ", biconex[i][j] + 1);
}
fprintf(out, "\n");
}
free(low);
free(disc);
free(parent);
fclose(in);
fclose(out);
return 0;
}