Pagini recente » Cod sursa (job #2398802) | Cod sursa (job #2548752) | Cod sursa (job #1990157) | Cod sursa (job #2569819) | Cod sursa (job #2157883)
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define MOD 1000000007
using namespace std;
typedef unsigned long long ll;
typedef pair< int , int > PII;
const int dirx[] = {-2, -1, 1, 2, 1, -1};
const int diry[] = {0, 1, 1, 0, -1, -1};
inline void debugMode()
{
#ifndef ONLINE_JUDGE
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
}
int n, m, Depth[100100], Low[100100];
bool viz[100100];
vector < int > V[100100];
stack < PII > St;
queue < set < int > > Q;
void dfs(int node, int dad, int depth){
viz[node] = 1;
Depth[node] = depth;
Low[node] = depth;
for (auto it: V[node]){
if (!viz[it]){
St.push({node, it});
dfs(it, node, depth + 1);
Low[node] = min(Low[node], Low[it]);
if (dad == -1 && V[node].size() > 1){
set < int > Ans;
while (St.top() != make_pair(node, it)){
PII E = St.top();
Ans.insert(E.x);
Ans.insert(E.y);
St.pop();
}
PII E = St.top();
Ans.insert(E.x);
Ans.insert(E.y);
Q.push(Ans);
St.pop();
}
else if (Low[it] >= Depth[node]){
set < int > Ans;
while (St.top() != make_pair(node, it)){
PII E = St.top();
Ans.insert(E.x);
Ans.insert(E.y);
St.pop();
}
PII E = St.top();
Ans.insert(E.x);
Ans.insert(E.y);
Q.push(Ans);
St.pop();
}
} else if (it != dad && Low[node] > Depth[it]){
Low[node] = Depth[it];
St.push({node, it});
}
}
}
int main(){
debugMode();
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0, x, y; i < m; i++){
cin >> x >> y;
V[x].pb(y);
V[y].pb(x);
}
for (int i = 1; i <= n; i++){
if (viz[i]) continue;
dfs(i, -1, 1);
set < int > Ans;
while (St.size()){
PII E = St.top();
Ans.insert(E.x);
Ans.insert(E.y);
St.pop();
}
if (Ans.size()) Q.push(Ans);
}
cout << Q.size() << "\n";
while (Q.size()){
set < int > Ans = Q.front();
for (auto it: Ans) cout << it << " ";
Q.pop();
cout << "\n";
}
return 0;
}