Pagini recente » Cod sursa (job #3002161) | Cod sursa (job #604213) | Cod sursa (job #1952127) | Cod sursa (job #839687) | Cod sursa (job #1379092)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 100000 + 1;
const int Mmax = 200000 + 1;
pair<int,int> stiva[Mmax];
vector<int> G[Nmax];
vector<int> BC[Nmax];
int lowIndex[Nmax], Index[Nmax];
int N, M, nrComp, top;
void biconex(int x, int y)
{
pair<int,int> E;
nrComp++;
do
{
E = stiva[top--];
BC[nrComp].push_back(E.first);
BC[nrComp].push_back(E.second);
} while ( E.first != x || E.second != y );
}
void dfs(int nod, int dad, int d)
{
lowIndex[nod] = Index[nod] = d;
for (int son: G[nod])
if ( son != dad )
{
if ( Index[son] == 0 )
{
stiva[ ++top ] = {nod, son};
dfs(son, nod, d + 1);
lowIndex[nod] = min(lowIndex[nod], lowIndex[son]);
if ( lowIndex[son] >= Index[nod] )
biconex(nod, son);
}
else
lowIndex[nod] = min(lowIndex[nod], Index[son]);
}
}
void printBC()
{
ofstream out("biconex.out");
out << nrComp << "\n";
for ( int i = 1; i <= nrComp; ++i )
{
sort(BC[i].begin(), BC[i].end());
BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());
for (int x: BC[i])
out << x << " ";
out << "\n";
}
out.close();
}
int main()
{
ifstream in("biconex.in");
ios_base::sync_with_stdio(false);
in >> N >> M;
for ( int i = 1; i <= M; ++i )
{
int a, b;
in >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1, 0, 1);
printBC();
return 0;
}