Pagini recente » Cod sursa (job #1010329) | Cod sursa (job #2792504) | Cod sursa (job #2471945) | Cod sursa (job #1502378) | Cod sursa (job #1100001)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define NMAX 100010
#define minim(a,b) ((a<b)?(a):(b))
int N, M;
int AnhazlKomponenten; // the number of biconex components
int Verbindung[NMAX]; // how much can I go up on the graph
int Tiefe[NMAX]; // depth
stack < pair < int , int > > Stapel;
vector < int > G[NMAX];
vector < int > Biconex[NMAX];
void Scannen()
{
freopen("biconex.in","r",stdin);
scanf("%d%d",&N,&M);
for(int i=1,x,y;i<=M;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void Berechnen(int Knoten1, int Knoten2)
{
int x,y;
AnhazlKomponenten++;
do{
x = Stapel.top().first;
y = Stapel.top().second;
Stapel.pop();
Biconex[AnhazlKomponenten].push_back(x);
Biconex[AnhazlKomponenten].push_back(y);
}while(x != Knoten1 || y != Knoten2);
}
void DFS(int Knoten, int Vater)
{
Verbindung [Knoten] = Tiefe[Knoten] = Tiefe[Vater] + 1;
for(vector < int > :: iterator it = G[Knoten].begin(); it != G[Knoten].end(); ++ it)
{
if(*it == Vater)
continue;
if(!Tiefe[*it])
{
Stapel.push(make_pair(Knoten, *it));
DFS(*it, Knoten);
Verbindung[Knoten] = minim(Verbindung[Knoten], Verbindung[*it]);
if(Verbindung[*it] >= Tiefe[Knoten])
Berechnen(Knoten, *it);
}
else
Verbindung[Knoten] = minim(Verbindung[Knoten], Tiefe[*it]);
}
}
void Drucken()
{
freopen("biconex.out", "w", stdout);
printf("%d\n",AnhazlKomponenten);
for(int i=1; i <= AnhazlKomponenten; i++)
{
sort(Biconex[i].begin(), Biconex[i].end());
int Alt = -1;
for(vector < int > :: iterator it = Biconex[i].begin(); it != Biconex[i].end(); ++ it)
{
if(Alt != *it)
printf("%d ",*it);
Alt = *it;
}
printf("\n");
}
}
int main()
{
Scannen();
DFS(1,0);
Drucken();
return 0;
}