Pagini recente » Cod sursa (job #2965655) | Cod sursa (job #2937139) | Cod sursa (job #1452358) | Cod sursa (job #1161854) | Cod sursa (job #2809063)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int NMAX = 100000;
int stck[NMAX], sp, lvl[NMAX], maxH[NMAX];
vector<int> edges[NMAX];
vector<vector<int>> bi;
int dfs(int node, int node_lvl)
{
lvl[node] = node_lvl;
maxH[node] = node_lvl;
stck[++sp] = node;
int len = edges[node].size(), i;
for (i = 0; i < len; i++)
{
if (lvl[edges[node][i]] == 0)
{
int aux = dfs(edges[node][i], node_lvl + 1);
maxH[node] = min(maxH[node], aux);
if (aux >= node_lvl)
{
bi.push_back(vector<int>());
while (sp >= 0 && stck[sp] != node)
{
bi.back().push_back(stck[sp]);
sp--;
}
bi.back().push_back(node);
}
}
else
maxH[node] = min(maxH[node], lvl[edges[node][i]]);
}
return maxH[node];
}
int main()
{
int n, m, v1, v2, i, j, len1, len2;
FILE *fin = fopen("biconex.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (i = 0; i < m; i++)
{
fscanf(fin, "%d%d", &v1, &v2);
v1--, v2--;
edges[v1].push_back(v2);
edges[v2].push_back(v1);
}
fclose(fin);
for (i = 0; i < n; i++)
if (lvl[i] == 0)
dfs(i, 1);
FILE *fout = fopen("biconex.out", "w");
len1 = bi.size();
fprintf(fout, "%d\n", len1);
for (i = 0; i < len1; i++)
{
len2 = bi[i].size();
for (j = 0; j < len2; j++)
fprintf(fout, "%d ", bi[i][j] + 1);
fprintf(fout, "\n");
}
fclose(fout);
return 0;
}