Pagini recente » Cod sursa (job #3349492) | Cod sursa (job #3263553) | Cod sursa (job #3337700) | Cod sursa (job #3339863) | Cod sursa (job #3333251)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100000;
int n,i,viz[NMAX+5],order[NMAX+5],low[NMAX+5],node1,node2,sol,m;
vector <int> bcc[NMAX+5];
vector <int> adj[NMAX+5];
stack <int> st;
void dfs(int node, int daddy)
{
viz[node]=1;
if (daddy==-1)
order[node]=1;
else
order[node]=order[daddy]+1;
low[node]=order[node];
st.push(node);
for (auto node2: adj[node])
{
if (node2==daddy)
continue;
if (viz[node2]==1)
low[node]=min(low[node],order[node2]);
else
{
dfs(node2,node);
low[node]=min(low[node],low[node2]);
if (low[node2]>=order[node])
{
sol++;
while (!st.empty() && st.top()!=node2)
{
bcc[sol].push_back(st.top());
st.pop();
}
bcc[sol].push_back(node2);
st.pop();
bcc[sol].push_back(node);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(nullptr); fout.tie(nullptr);
fin>>n>>m;
while (m--)
{
fin>>node1>>node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
for (i=1; i<=n; i++)
{
if (!viz[i])
dfs(i,-1);
}
fout<<sol<<'\n';
for (i=1; i<=sol; i++)
{
for (auto x: bcc[i])
fout<<x<<" ";
fout<<'\n';
}
return 0;
}