Pagini recente » Cod sursa (job #901903) | Cod sursa (job #2715822) | Cod sursa (job #2883430) | Cod sursa (job #1912634) | Cod sursa (job #603125)
Cod sursa(job #603125)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
#define x first
#define y second
#define NMax 100005
using namespace std;
vector <int> G[NMax];
stack < pair <int, int> > Edge;
vector < vector <int> > BC;
int N, Level[NMax], LowestL[NMax];
void Read ()
{
ifstream fin ("biconex.in");
int M, X, Y;
fin >> N >> M;
for (int i=1; i<=N; ++i)
{
Level[i]=-1;
}
for (; M>0; --M)
{
fin >> X >> Y;
G[X].push_back (Y);
G[Y].push_back (X);
}
fin.close ();
}
void Type ()
{
ofstream fout ("biconex.out");
fout << BC.size () << "\n";
for (unsigned i=0; i<BC.size(); ++i)
{
sort(BC[i].begin(), BC[i].end());
BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());
for (unsigned j=0; j<BC[i].size(); ++j)
{
fout << BC[i][j] << " ";
}
fout << "\n";
}
fout.close ();
}
inline int Min (int a, int b)
{
if (a<b)
{
return a;
}
return b;
}
inline int Max (int a, int b)
{
if (a>b)
{
return a;
}
return b;
}
void DetBC (int X, int Y)
{
vector <int> Component;
int cx, cy;
do
{
cx=Edge.top ().x;
cy=Edge.top ().y;
Edge.pop ();
Component.push_back (cx);
Component.push_back (cy);
}
while (cx!=X || cy!=Y);
BC.push_back (Component);
}
void DFS (int X, int F, int L)
{
vector <int> :: iterator V;
LowestL[X]=Level[X]=L;
for (V=G[X].begin (); V!=G[X].end (); ++V)
{
if (*V==F)
{
continue;
}
if (Level[*V]==-1)
{
Edge.push (make_pair (X, *V));
DFS (*V, X, L+1);
LowestL[X]=Min (LowestL[X], LowestL[*V]);
if (LowestL[*V]>=Level[X])
{
DetBC (X, *V);
}
}
else
{
LowestL[X]=Min (LowestL[X], Level[*V]);
}
}
}
int main ()
{
Read ();
DFS (1, 0, 0);
Type ();
return 0;
}