Pagini recente » Cod sursa (job #3214964) | Concursuri | Cod sursa (job #1490640) | Cod sursa (job #677914) | Cod sursa (job #1386051)
#include <bits/stdc++.h>
using namespace std;
#define VI vector<int>
#define PII pair<int, int>
const int MAXN = 1e5 + 5;
vector<int> G[MAXN];
vector<int> seen, lowPoint, depth;
vector<PII> st;
vector<VI> comps;
void dfs(int node, int f) {
seen[node] = 1;
lowPoint[node] = depth[node];
for(auto tmp : G[node]) {
if(tmp == f)
continue;
if(!seen[tmp]) {
depth[tmp] = depth[node] + 1;
st.push_back(make_pair(node, tmp));
dfs(tmp, node);
lowPoint[node] = min(lowPoint[tmp], lowPoint[node]);
if(lowPoint[tmp] >= depth[node]) {
unordered_set<int> newComp;
bool doneLastOne = false;
while(!st.empty() && !doneLastOne) {
newComp.insert(st.back().first);
newComp.insert(st.back().second);
if(st.back().first == node && st.back().second == tmp)
doneLastOne = true;
st.pop_back();
}
vector<int> newCompSol;
for(auto tmp : newComp)
newCompSol.push_back(tmp);
comps.push_back(newCompSol);
}
} else {
lowPoint[node] = min(lowPoint[node], depth[tmp]);
}
}
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m; cin >> n >> m;
for(int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
--a, --b;
G[a].push_back(b);
G[b].push_back(a);
}
seen = vector<int> (n, 0);
lowPoint = vector<int> (n, 0);
depth = vector<int> (n, 0);
for(int i = 0; i < n; ++i)
if(!seen[i])
dfs(i, -1);
cout << comps.size() << "\n";
for(auto comp: comps) {
for(auto tmp : comp)
cout << tmp + 1 << " ";
cout << "\n";
}
}