Pagini recente » Cod sursa (job #1388626) | Cod sursa (job #1531894) | Cod sursa (job #2784060) | Cod sursa (job #1343123) | Cod sursa (job #2983251)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N = 1e5 + 5;
int n, m;
vector <int> g[N];
bool articulatie[N];
int t_min[N], t_in[N];
int timer;
vector <vector <int>> cbc;
stack <int> stiva;
void adauga(int x, int y, vector <int> &v)
{
while(stiva.top() != y)
{
v.push_back(stiva.top());
stiva.pop();
}
v.push_back(y);
stiva.pop();
v.push_back(x);
}
void dfs(int node, int par)
{
t_min[node] = t_in[node] = ++timer;
stiva.push(node);
int nr_fii = 0;
for(auto fiu:g[node])
{
if(fiu == par)
continue;
if(t_in[fiu] == 0)
{
dfs(fiu, node);
nr_fii++;
t_min[node] = min(t_min[node], t_min[fiu]);
if(t_min[fiu] >= t_in[node])
{
articulatie[node] = true;
vector <int> c;
adauga(node, fiu, c);
cbc.push_back(c);
}
}
else
{
t_min[node] = min(t_min[node], t_in[fiu]);
}
}
if(par == 0 && nr_fii > 1)
{
articulatie[node] = true;
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++)
{
if(t_in[i] == 0)
{
dfs(i, 0);
}
}
out << cbc.size() << '\n';
for(auto comp:cbc)
{
for(auto x:comp)
{
out << x << ' ';
}
out << '\n';
}
return 0;
}