Pagini recente » Cod sursa (job #1518324) | Cod sursa (job #172342) | Cod sursa (job #1061282) | Cod sursa (job #1736914) | Cod sursa (job #838120)
Cod sursa(job #838120)
#include <fstream>
#include <stdio.h>
#include <vector>
#include <stack>
#define MAX_SIZE 100000
#include <algorithm>
#include <string.h>
using namespace std;
vector <int> graf[MAX_SIZE+1];
stack <int> parcurgere;
vector <int> biconexe[MAX_SIZE +1];
int tati[MAX_SIZE + 1];
int sel[MAX_SIZE+1];
int level[MAX_SIZE + 1];
int N , M ,nr = 0;
char ap[MAX_SIZE];
void create_component(int nod)
{
memset(ap,0,MAX_SIZE);
nr++;
while (parcurgere.top() != nod)
{
if (ap[parcurgere.top()] != 1)
{
biconexe[nr].push_back(parcurgere.top());
ap[parcurgere.top()] = 1;
}
parcurgere.pop();
}
if (ap[parcurgere.top()] != 1)
{
biconexe[nr].push_back(parcurgere.top());
}
sort(biconexe[nr].begin(), biconexe[nr].end());
}
void DF(int nod , int nivel)
{
sel[nod] = nivel;
level[nod] = nivel;
parcurgere.push(nod);
for (int i = 0;i<graf[nod].size();i++)
{
int x = graf[nod][i];
if (sel[x] == -1)
{
tati[x] = nod;
DF(x , nivel + 1);
sel[nod] = min(sel[nod],sel[x]);
if ( sel[x] >= level[nod])
{
create_component(nod);
}
}
else
{
if ( tati[nod] != x)
{
sel[nod] = min(sel[nod],level[x]);
}
}
}
}
int main()
{
ifstream input("biconex.in");
ofstream output("biconex.out");
input >> N >> M;
for (int i =0;i<M;i++)
{
int x , y;
input >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for (int i =0;i<=MAX_SIZE;i++)
{
sel[i] = -1;
}
for (int i =1;i<=N;i++)
{
if (sel[i] == -1)
{
DF(i,1);
}
}
output << nr;
for (int i =1;i<=nr;i++)
{
output << "\n";
for (int j =0;j<biconexe[i].size();j++)
{
output << biconexe[i][j] << " ";
}
}
input.close();
output.close();
return 0;
}