Pagini recente » Cod sursa (job #2113984) | Cod sursa (job #1690030) | Cod sursa (job #1699465) | Cod sursa (job #3329214) | Cod sursa (job #3325775)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> adj[100005];
int lvl[100005], low[100005], cnt = 1;
bool visited[100005];
stack <pair<int, int>> s;
set <int> cmp[100005];
void dfs(int node, int dad) {
visited[node] = 1;
low[node] = lvl[node] = lvl[dad] + 1;
for(auto x : adj[node]) {
if(x == dad)
continue;
if(visited[x]) {
low[node] = min(low[node], low[x]);
continue;
}
s.push({x, node});
dfs(x, node);
low[node] = min(low[node], low[x]);
if(lvl[node] <= low[x]) {
while(true) {
int n1 = s.top().first, n2 = s.top().second;
s.pop();
cmp[cnt].insert(n1);
cmp[cnt].insert(n2);
if(x == n1 && node == n2)
break;
}
cnt++;
}
}
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 1);
if(s.empty())
cnt--;
while(!s.empty()) {
int n1 = s.top().first, n2 = s.top().second;
s.pop();
cmp[cnt].insert(n1);
cmp[cnt].insert(n2);
}
cout << cnt << '\n';
for(int i = 1; i <= cnt; i++) {
for(auto x : cmp[i])
cout << x << ' ';
cout << '\n';
}
}