Pagini recente » Cod sursa (job #527308) | Cod sursa (job #1533647) | Cod sursa (job #468148) | Cod sursa (job #2242863) | Cod sursa (job #2676622)
#include <bits/stdc++.h>
using namespace std;
#define FINAL
#ifdef FINAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif
const int NMAX = 100007;
vector<int> g[NMAX];
int indecs[NMAX], lowlink[NMAX];
stack<pair<int, int>> st;
vector<vector<int>> comps;
void make_comp(int root, int son)
{
vector<int> ret;
int f, s;
do
{
f = st.top().first;
s = st.top().second;
st.pop();
ret.push_back(f);
ret.push_back(s);
}
while(f != root && s != son);
comps.push_back(ret);
}
void dfs(int root, int father, int depth)
{
indecs[root] = lowlink[root] = depth;
for(auto vec : g[root])
{
if(vec == father) continue;
if(indecs[vec] == 0)
{
st.push(make_pair(root, vec));
dfs(vec, root, depth + 1);
lowlink[root] = min(lowlink[root], lowlink[vec]);
if(lowlink[vec] >= indecs[root])
make_comp(root, vec);
}
else
{
lowlink[root] = min(lowlink[root], indecs[vec]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
for(int i = 0; i < m; i++)
{
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, -1, 1);
for(auto &comp : comps)
{
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
}
cout << comps.size() << '\n';
for(auto comp : comps)
{
for(auto elem : comp)
cout << elem << ' ';
cout << '\n';
}
return 0;
}