Pagini recente » Cod sursa (job #372800) | Cod sursa (job #2005662) | Cod sursa (job #2895707) | Cod sursa (job #1486420) | Cod sursa (job #2835396)
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int maxN = 1e5 + 5;
const int maxM = 2e5 + 5;
vector <int> g[maxN];
set <int> componenta[maxN];
vector <pair<int,int>> muchii;
bool check[maxN];
int tin[maxN], low[maxN], pas = 0, length = 0;
void comp_noua(int u, int v) {
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(u == a && v == b)
return ;
}
}
void dfs(int node, int p = -1) {
check[node] = true;
tin[node] = low[node] = ++pas;
for(int to : g[node]) {
if(to == p) continue;
if(check[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 v : componenta[i])
fout << v << " ";
return 0;
}