Pagini recente » Cod sursa (job #127783) | Cod sursa (job #2486598) | Cod sursa (job #1648628) | Cod sursa (job #2091856) | Cod sursa (job #2797844)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int n,m,S,F;
vector<int> la[100005];
int lowLink[100005];
int ids[100005];
int id = 1;
stack<pair<int,int>> st;
vector<vector<int>> vcc;
void dfs_critice(int s)
{
lowLink[s] = id;
ids[s] = id;
id++;
for (auto& to: la[s])
{
if (ids[to] != -1)
{
lowLink[s] = min(lowLink[s], ids[to]);
//cout << s << ' ' << to << ' ' << lowLink[s] << ' ' << ids[to] << '\n';
}
else
{
st.push({s,to});
dfs_critice(to);
lowLink[s] = min(lowLink[s], lowLink[to]);
//cout << s << ' ' << to << ' ' << lowLink[s] << '\n';
if (lowLink[to] >= ids[s])
{
vector<int> cc;
while (st.top().first != from && st.top().second != to)
{
cc.push_back(st.top().second);
st.pop();
}
cc.push_back(st.top().first);
cc.push_back(st.top().second);
st.pop();
vcc.push_back(cc);
}
}
}
}
int main()
{
f >> n >> m;
for (int i = 0; i < m; i++)
{
int x,y;
f >> x >> y;
la[x].push_back(y);
la[y].push_back(x);
}
for (int i = 1; i <= n; i++)
ids[i] = -1;
dfs_critice(1);
g << vcc.size() << '\n';
for (auto& row: vcc)
{
for (auto el: row)
g << el << ' ';
g << '\n';
}
return 0;
}