Pagini recente » Cod sursa (job #1295225) | Monitorul de evaluare | Cod sursa (job #17026) | Cod sursa (job #2255748) | Cod sursa (job #853947)
Cod sursa(job #853947)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> vecini[100009];
vector <int> solutie[100009];
vector <int> stack;
int totmaisus[100009];
int catdesus[100009];//nivelul
int viz[100009];
int n,m,nr;
void init(){
for (int i=1;i<=n;i++){
viz[i]=0;
}
}
void citeste(){
in>>n>>m;
for (int i=1;i<=m;i++){
int x,y;
in>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
}
void parc_ad(int nod,int nivel, int tata){
totmaisus[nod]=nivel;
catdesus[nod]=nivel;
stack.push_back(nod);
for (int i=0;i<vecini[nod].size();i++)
{
int x=vecini[nod][i];
if (catdesus[x]==0)
{
stack.push_back(nod);
parc_ad(x,nivel+1,nod);
if (totmaisus[nod]>totmaisus[x]){
totmaisus[nod]=totmaisus[x];
}else
if (totmaisus[x]>=nivel){
int m=stack.size()-1;
int j;
nr++;
while (nod!=stack[m]){
if (viz[stack[m]]==0){
solutie[nr].push_back(stack[m]);
viz[stack[m]]=1;
}
--m;
stack.pop_back();
}
if (viz[stack[m]]==0) {
solutie[nr].push_back(stack[m]);
}
stack.pop_back();
for(int j=0;j<solutie[nr].size();j++)
viz[solutie[nr][j]]=0;
}
}else
if ((catdesus[x]<totmaisus[nod]) && x!=tata)
totmaisus[nod]=catdesus[x];
}
}
int main(){
init();
int i,j;
citeste();
for ( i=1;i<=n;i++)
if (catdesus[i]==0) parc_ad(i,1,0);
out<<nr<<'\n';
for ( i=1;i<=nr;i++){
for (j=0;j<solutie[i].size();j++)
out<<solutie[i][j]<<' ';
out<<'\n';
}
return 0;
}