Pagini recente » Cod sursa (job #1674558) | Cod sursa (job #311741) | Cod sursa (job #1568897) | Cod sursa (job #1247215) | Cod sursa (job #2831887)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector < int > v[100005];
int n,m,x,y;
int disc[100005],low[100005],parent[100005],ap[100005],child[100005];
vector < vector < int > > comps;
vector < int > bcnx;
int timp;
stack < pair < int , int > > st;
void read() {
f >> n >> m;
for (int i=1;i<=m;i++) {
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void create_comp(int a, int b) {
x = st.top().first; y=st.top().second;
while (x!=a && y!=b) {
bcnx.push_back(y);
st.pop();
x = st.top().first; y=st.top().second;
}
bcnx.push_back(x);
bcnx.push_back(y);
st.pop();
comps.push_back(bcnx);
bcnx.clear();
}
void dfs(int nod) {
timp++;
low[nod]=timp; disc[nod]=timp;
for (auto k:v[nod]) {
if (disc[k]==0) {
st.push({nod,k});
child[nod]++;
parent[k] = nod;
dfs(k);
low[nod] = min(low[nod],low[k]);
if (low[k]>=disc[nod]) {
ap[nod]=1;
create_comp(nod,k);
}
}
else if (parent[nod]!=k) {
low[nod] = min(low[nod],disc[k]);
}
}
}
void solve() {
for (int i=1;i<=n;i++) {
if (disc[i]==0) {
dfs(i);
}
}
}
void show() {
g << comps.size() << '\n';
for (int i=0;i<comps.size();i++) {
for (int k:comps[i]) {
g << k << " ";
}
g << '\n';
}
}
int main()
{
read();
solve();
show();
return 0;
}