Pagini recente » Cod sursa (job #3177002) | Cod sursa (job #1543743) | Cod sursa (job #948880) | Cod sursa (job #2778239) | Cod sursa (job #1703533)
/// Programul determina muchiile critice. Din fiecare muchie critica se obtin doua componente conexe:
/// capetele (noduri ale) muchiei + ceea ce ramane in urma eliminarii muchiei din arbore
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N = 1002;
int vecin[N][N]; /// Adiacente; to-do: lista de adiacente (problema cu marcajul back edge-urilor), merge si un vector de tati
int fol[N]; /// fol[i] = 1 daca am parcurs deja muchia 'i'
int level[N]; /// Nivelul in arbore
int dfn[N]; /// Depth First Number = nivelul minim al stramosului la care pot ajunge
int n,m,cnt;
void afis()
{
int i,j;
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j) out<<vecin[i][j]<<" ";
out<<"\n";
}
out<<"\n";
}
void dfs(int poz)
{
int i,fiu;
fol[poz] = 1;
for(i=1; i<=n; ++i)
{
fiu = i;
if(fol[fiu] == 0 && vecin[poz][i] == 1) /// Forward edge --> DFS
{
vecin[poz][i] = vecin[i][poz] = 2; /// Marchez cross edge
level[fiu] = level[poz] + 1; /// Initializez fiul (am nevoie de tata, e mai bine sa pun instructiunile aici decat la inceputul functiei)
dfn[fiu] = level[fiu];
dfs(fiu);
dfn[poz] = min(dfn[poz], dfn[fiu]); /// Preiau dfn-ul fiului (desigur, daca este mai mic)
}
if(fol[fiu] == 1 && vecin[poz][i] == 1) /// Back edge --> actualizez Dfn
dfn[poz] = min(dfn[poz], level[fiu]);
}
}
void dfs_afis(int poz) /// Pt afisarea componentelor biconexe
{
int i;
fol[poz] = 1;
out<<poz<<" ";
for(i=1; i<=n; ++i)
if(vecin[poz][i] != 0 && fol[i] == 0)
{
vecin[poz][i] = vecin[i][poz] = 0;
dfs_afis(i);
}
}
int are_fii(int poz) /// O brutalitate. Verific daca nodul 'poz' este izolat sau nu
{
int i;
for(i=1; i<=n; ++i)
if(vecin[poz][i] == 1)
return 1;
return 0;
}
int main()
{
int i,j,a,b;
in>>n>>m;
for(i=1; i<=m; ++i)
{
in>>a>>b;
vecin[a][b] = vecin[b][a] = 1;
}
//for(i=1; i<=n; ++i) dfn[i] = N;
//afis();
dfn[1] = 1; /// Initializez radacina (mult mai elegant ar fi sa leg o pseudo-radacina '0' la nodul 1, ca sa scap de initailizari)
level[1] = 1;
dfs(1);
//cout<<"index: "; for(i=1; i<=n; ++i) cout<<i<<" "; cout<<"\n";
//cout<<"level: "; for(i=1; i<=n; ++i) cout<<level[i]<<" "; cout<<"\n";
//cout<<"dfn: "; for(i=1; i<=n; ++i) cout<<dfn[i]<<" "; cout<<"\n";
//afis();
for(i=1; i<=n; ++i) /// Aflu numarul componentelor biconexe
for(j=i+1; j<=n; ++j)
if(vecin[i][j] != 0 && dfn[j] == level[j])
{
cout<<"Muchia ("<<i<<", "<<j<<") este critica\n";
++cnt;
}
cnt *= 2;
out<<cnt<<"\n";
for(i=1; i<=n; ++i) /// Elimin muchiile critice, afisez cele doua noduri
for(j=i+1; j<=n; ++j)
if(vecin[i][j] != 0 && dfn[j] == level[j])
{
vecin[i][j] = vecin[j][i] = 0;
out<<i<<" "<<j<<"\n";
}
for(i=1; i<=n; ++i) fol[i] = 0; /// Reinitializez fol[] pentru o noua parcurgere
for(i=1; i<=n; ++i) /// Afisez componentele biconexe ramase
if(fol[i] == 0 && are_fii(i))
{
dfs_afis(i);
out<<"\n";
}
return 0;
}