Pagini recente » Cod sursa (job #1040811) | Cod sursa (job #577785) | Cod sursa (job #648923) | Cod sursa (job #1116703) | Cod sursa (job #3296777)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, k, niv[100005], low[100005], nr_fii;
int st[100005], top;
bool viz[100005];
vector<int> G[100005];
vector<int> componente[200005];
void Biconexitate(int x, int tata)
{
int i;
viz[x] = 1;
niv[x] = low[x] = niv[tata] + 1;
st[++top] = x;
for(int e : G[x])
if(e != tata)
{
if(viz[e] == 1)
low[x] = min(low[x], niv[e]);
else{
Biconexitate(e, x);
low[x] = min(low[x], low[e]);
if(x == 1) nr_fii++;
if(niv[x] <= low[e])
{
k++;
do{
i = st[top--];
componente[k].push_back(i);
}while(i != e);
componente[k].push_back(x);
}
}
}
}
int main()
{
int i, j;
fin >> n >> m;
while(m)
{
fin >> i >> j;
G[i].push_back(j);
G[j].push_back(i);
m--;
}
Biconexitate(1, 0);
fout << k << "\n";
while(k)
{
for(int e : componente[k])
fout << e << " ";
fout << "\n";
k--;
}
fout.close();
return 0;
}