Pagini recente » Cod sursa (job #834730) | Cod sursa (job #644445) | Cod sursa (job #1424806) | Cod sursa (job #337642) | Cod sursa (job #2045829)
#include <bits/stdc++.h>
using namespace std;
stack <pair<int, int>> solve;
vector <int> graf[100001];
vector <int> componente[100001];
int cate_componente;
int level[100001], minim[100001];
void construieste (int comp, int x, int y)
{
int a, b;
while (true)
{
a = solve.top().first;
b = solve.top().second;
solve.pop();
if (a == x && b == y)
{
componente[comp].push_back(a);
componente[comp].push_back(b);
return;
}
componente[comp].push_back(a);
componente[comp].push_back(b);
}
}
void dfs (int nod, int tata, int nivel)
{
level[nod] = minim[nod] = nivel;
for (auto x:graf[nod])
{
if (x!=tata)
{
if (level[x] == 0)
{
solve.push(make_pair(nod, x));
dfs(x, nod, nivel+1);
if (minim[x]>=level[nod])
{
++cate_componente;
construieste (cate_componente, nod, x);
}
minim[nod] = min(minim[nod], minim[x]);
}
else minim[nod] = min(minim[nod], minim[x]);
}
}
}
int main()
{
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int n, m;
fin >> n >> m;
for (int i = 1; i<=m; ++i)
{
int x, y;
fin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
dfs(1, 0, 1);
fout << cate_componente << '\n';
for (int i = 1; i<=cate_componente; ++i)
{
sort (componente[i].begin(), componente[i].end());
int vechi = 0;
for (auto x:componente[i])
if (x!=vechi)
{
vechi = x;
fout << x << " ";
}
fout << '\n';
}
return 0;
}