Pagini recente » Cod sursa (job #183530) | Cod sursa (job #1474731) | Cod sursa (job #1304805) | Cod sursa (job #1867235) | Cod sursa (job #1821918)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100000;
vector<int> g[MAX + 1], bc[MAX + 1];
int nrbc;
pair<int, int> st[MAX + 1];
int top;
int dfn[MAX + 1], low[MAX + 1];
void biconex(int x, int y)
{
nrbc++;
pair<int, int> p = {x, y}, q;
q = st[top];
top--;
while(p != q)
{
bc[nrbc].push_back(q.first);
bc[nrbc].push_back(q.second);
q = st[top];
top--;
}
bc[nrbc].push_back(q.first);
bc[nrbc].push_back(q.second);
}
void dfs(int nod, int nr)
{
dfn[nod] = low[nod] = nr;
for(int i = 0; i < g[nod].size(); i++)
if(dfn[g[nod][i]] == 0)
{
st[++top] = {nod, g[nod][i]};
dfs(g[nod][i], nr + 1);
low[nod] = min(low[nod], low[g[nod][i]]);
if(low[g[nod][i]] >= dfn[nod])
biconex(nod, g[nod][i]);
}
else
low[nod] = min(low[nod], dfn[g[nod][i]]);
}
int main()
{
FILE *fin, *fout;
fin = fopen("biconex.in", "r");
fout = fopen("biconex.out", "w");
int n, m;
fscanf(fin, "%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int x, y;
fscanf(fin, "%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 1);
fprintf(fout, "%d\n", nrbc);
for(int i = 1; i <= nrbc; i++)
{
sort(bc[i].begin(), bc[i].end());
bc[i].erase(unique(bc[i].begin(), bc[i].end()), bc[i].end());
for(int j = 0; j < bc[i].size(); j++)
fprintf(fout, "%d ", bc[i][j]);
fprintf(fout, "\n");
}
return 0;
}