Pagini recente » Cod sursa (job #703515) | Cod sursa (job #2291163) | Cod sursa (job #3132551) | Cod sursa (job #2331478) | Cod sursa (job #2173916)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 100005;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct muchie{
int x,y;
}vect[2*N];
vector <int> V[N];
vector <int> Muchii[N];
vector <int> sol[N];
vector <int> mult[N];
stack <int> s;
int low[N],niv[N];
bool isParc[N];
int n,m,nr,cif;
void dfs(int poz,int lst){
int sz = V[poz].size();
cif++;
low[poz] = cif;
niv[poz] = cif;
for(int i = 0; i< sz; i++){
int mch = Muchii[poz][i];
int ad = V[poz][i];
if(niv[ad]==0){
s.push(mch);
dfs(ad,poz);
low[poz] = min(low[poz],niv[ad]);
low[poz] = min(low[poz],low[ad]);
if(niv[poz]<low[ad]){
nr++;
sol[nr].push_back(poz);
sol[nr].push_back(ad);
}
}
else if(niv[ad]<niv[poz]&&ad!=lst){
low[poz] = min(low[poz],low[ad]);
low[ad] = low[poz];
}
}
mult[low[poz]].push_back(poz);
}
int main(){
f>>n>>m;
for(int i =1; i<= m; i++){
int x,y;
f>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
Muchii[x].push_back(i);
Muchii[y].push_back(i);
vect[i].x = x;
vect[i].y = y;
}
dfs(1,0);
for(int i =1; i<= n; i++){
//g<<i<<" "<<niv[i]<<" "<<low[i]<<"\n";
}
for(int i = 1; i<= n; i++){
int sz = mult[i].size();
if(sz>1){
nr++;
for(int j =0; j< sz; j++){
sol[nr].push_back(mult[i][j]);
//g<<mult[i][j]<<" ";
}
//g<<"\n";
}
}
g<<nr<<"\n";
for(int i =1; i<= nr; i++){
int sz = sol[i].size();
sort(sol[i].begin(),sol[i].end());
for(int j =0; j< sz; j++){
g<<sol[i][j]<<" ";
}
g<<"\n";
}
f.close();
g.close();
return 0;
}