Pagini recente » Cod sursa (job #1924662) | Cod sursa (job #2346284) | Cod sursa (job #3250220) | Cod sursa (job #1316266) | Cod sursa (job #595289)
Cod sursa(job #595289)
#include <iostream>
#include <fstream>
#include <vector>
#define x first
#define y second
using namespace std;
vector <int> G[100005], BC[100005];
vector < pair <int, int> > Edge;
int N, Level[100005], LowestL[100005], NBC;
bool Component[100005];
void Read ()
{
ifstream fin ("biconex.in");
int i, M, X, Y;
fin >> N >> M;
for (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");
int i, j;
fout << NBC << "\n";
for (i=0; i<NBC; ++i)
{
for (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)
{
int i, x, y;
for (i=1; i<=N; ++i)
{
Component[i]=false;
}
Component[X]=true;
Component[Y]=true;
x=Edge[Edge.size ()-1].x;
y=Edge[Edge.size ()-1].y;
while ((x!=X) || (y!=Y))
{
Component[x]=true;
Component[y]=true;
Edge.pop_back ();
x=Edge[Edge.size ()-1].x;
y=Edge[Edge.size ()-1].y;
}
Edge.pop_back ();
for (i=1; i<=N; ++i)
{
if (Component[i]==true)
{
BC[NBC].push_back (i);
}
}
NBC++;
}
void DFS (int X, int F, int L)
{
vector <int> :: iterator V;
Level[X]=L;
LowestL[X]=L;
for (V=G[X].begin (); V!=G[X].end (); ++V)
{
if (*V!=F)
{
if (Level[*V]==-1)
{
Edge.push_back (make_pair (Min (X, *V), Max (X, *V)));
DFS (*V, X, L+1);
LowestL[X]=Min (LowestL[X], LowestL[*V]);
if (LowestL[*V]>=Level[X])
{
DetBC (Min (X, *V), Max (X, *V));
}
}
else
{
LowestL[X]=Min (LowestL[X], Level[*V]);
}
}
}
}
int main ()
{
Read ();
DFS (1, 0, 0);
Type ();
return 0;
}