Pagini recente » Cod sursa (job #936452) | Cod sursa (job #479711) | Cod sursa (job #905857) | Cod sursa (job #1502781) | Cod sursa (job #2338171)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> CompBicon[100005];
vector <int> L[100005];
int n, m, viz[100005], niv[100005], low[100005], nrComponente;
stack <int> st;
void DFS(int nod, int tata, int rad)
{
viz[nod] = 1;
niv[nod] = low[nod] = 1 + niv[tata];
st.push(nod);
for(auto fiu : L[nod])
if(fiu != tata)
{
if(viz[fiu])
{
low[nod] = min(low[nod], low[fiu]);
continue;
}
DFS(fiu, nod, rad);
low[nod] = min(low[nod], low[fiu]);
if(low[fiu] >= niv[nod])
{
nrComponente++;
int x;
do
{
x = st.top();
st.pop();
CompBicon[nrComponente].push_back(x);
}
while(x != fiu);
CompBicon[nrComponente].push_back(nod);
}
}
}
int main()
{
int x, y;
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
DFS(i, 0, i);
fout << nrComponente << "\n";
for(int i = 1; i <= nrComponente; i++)
{
for(int j = 0; j < CompBicon[i].size(); j++)
fout << CompBicon[i][j] << " ";
fout << "\n";
}
return 0;
}