Pagini recente » Cod sursa (job #1041229) | Cod sursa (job #554707) | Cod sursa (job #292318) | Cod sursa (job #1134138) | Cod sursa (job #2472112)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream cin("biconex.in");
std::ofstream cout("biconex.out");
using namespace std;
#define maxn 200030
#define min2(a,b) a<b?a:b
vector <int> adj[maxn]; //graf
int dfn[maxn],low[maxn],N,M;
vector <vector<int>> C;//componente biconexe
stack <pair<int,int>> stk; //depozitare laturi +comp biconexe
void citire(){
int x,y;
cin>>N>>M;
for(;M--;){
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void cache_clear(int x,int y){//adauga o comp biconexa
vector <int> comp_bicon; //la rezultat(C)
int tx,ty;
while(tx!=x||ty!=y){
tx=stk.top().first; ty=stk.top().second;
stk.pop();
comp_bicon.push_back(tx); comp_bicon.push_back(ty);
}
C.push_back(comp_bicon);
}
void dfs_anc(int n, int fn, int number) //fn nod anterior
{
vector <int>::iterator it;
low[n]=dfn[n]=number;
for(it=adj[n].begin();it!=adj[n].end();it++){
if(*it==fn) //daca nod ant ==not actual
continue;
if(!dfn[*it]){
stk.push(make_pair(n,*it));
dfs_anc(*it,n,number+1);
low[n]=min2(low[*it],low[n]);
if(dfn[n]<=low[*it])
cache_clear(n,*it);
}
else
low[n]=min2(dfn[*it],low[n]);//dfn[*it] pt ca are deja o val mai veche
}//dfn retine val initiale
}//low valorile minime de parcurgere
int main()
{
citire();
dfs_anc(1,-1,1);
cout<<C.size()<<'\n';
for(unsigned int i=0;i<C.size();i++){
sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
//Linia de mai sus sterge tot de dupa poz care o returneaza unique, pana la end()
//Unique sterge toate elementele care se repeta, mutand restul catre stanga si
//returneaza pozitia ultimului elem+1.
//Asa merge sa retina cate elem exact are C[i]
//erase e din <vector> unique e din <algorithm>
vector<int>::iterator it;
for(it=C[i].begin();it!=C[i].end();it++)
cout<<*it<<' ';//nu e nevoie de iterator
cout<<'\n';//la citire pt ca nu prea modificam
} //ar fi fost bine si un alt unsigned int for si C[i][j];
}