Pagini recente » Cod sursa (job #1063473) | Cod sursa (job #536787) | Cod sursa (job #3180020) | Cod sursa (job #539605) | Cod sursa (job #2917203)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int maxN = 1e5 + 5;
int timp = 0, length = 0;
int low[maxN], tin[maxN];
bool visit[maxN];
vector <pair<int,int>> muchii;
vector <int> g[maxN];
set <int> componenta[maxN];
void comp_noua (int node, int to) {
length += 1;
while(true) {
int a = muchii.back().first, b = muchii.back(). second;
muchii.pop_back();
componenta[length].insert(a);
componenta[length].insert(b);
if(node == a && to == b)
return ;
}
}
void dfs(int node, int dad = -1) {
visit[node] = true;
tin[node] = low[node] = ++timp;
for(int to : g[node]) {
if(to == dad) continue;
if(visit[to]) {
low[node] = min(low[node], tin[to]);
} else {
muchii.push_back({node, to});
dfs(to, node);
low[node] = min(low[node], low[to]);
if(low[to] >= tin[node])
comp_noua(node, to);
}
}
}
int main()
{
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; ++i) {
int u, v; fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
fout << length << '\n';
for(int i = 1; i <= length; ++i, fout << '\n')
for(auto j : componenta[i])
fout << j << " ";
return 0;
}