Pagini recente » Cod sursa (job #1102293) | Cod sursa (job #165486) | Cod sursa (job #2793841) | Cod sursa (job #1948403) | Cod sursa (job #2180058)
#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
struct nod{
//int index;
int level;
int min_level; /// dfn
int min_father_index;
};
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> veciniCopy[N];
vector<int> vecini[N];
int viz[N];
nod v[N];
int n,m;
void input(){
in>>n>>m;
for(int i=0; i<m; ++i){
int a,b;
in>>a>>b;
vecini[a].push_back(b);
vecini[b].push_back(a);
veciniCopy[a].push_back(b);
veciniCopy[b].push_back(a);
}
}
void output(){
vector<int> components[N];
for(int i=1; i<=n; ++i)
components[v[i].min_father_index].push_back(i);
/// Count Subgraphs
int count_subgraphs = 0;
for(auto &c : components)
if(c.size() > 1)
++count_subgraphs;
for(int i=1; i<=n; ++i)
for(auto &vecin : veciniCopy[i])
if(i <= vecin)
if(v[i].min_father_index != v[vecin].min_father_index)
++count_subgraphs;
out<<count_subgraphs<<"\n";
/// Print Subgraphs
for(auto &c : components){ /// Print subgraphs of min. size 2
if(c.size() > 1) {
for(auto &node : c) {
out<<node<<" ";
}
out<<"\n";
}
}
for(int i=1; i<=n; ++i) /// Print critical edge subgraphs
for(auto &vecin : veciniCopy[i])
if(i <= vecin) /// Don't print duplicates!
if(v[i].min_father_index != v[vecin].min_father_index)
out<<i<<" "<<vecin<<"\n";
}
void afis_vecini(){
for(int i=1; i<=n; ++i){
cout<<i<<": ";
for(auto &x : vecini[i])
cout<<x<<" ";
cout<<"\n";
}cout<<"\n";
}
void afis_noduri(){
for(int i=1; i<=n; ++i){
cout<<i<<": level = "<<v[i].level<<", min_level = "<<v[i].min_level<<", min_father_index = "<<v[i].min_father_index<<"\n";
}
}
void find_min_level(int index, int level){
if(viz[index] == 1)
return;
///cout<<"Visiting "<<index<<"\n";
if(index == 30 || index == 10){
int a=5;
}
v[index].level = level;
v[index].min_level = level;
v[index].min_father_index = index;
viz[index] = 1;
//for(auto vecinIndex : vecini[index]){
while(vecini[index].begin() != vecini[index].end()){
int vecinIndex = *(vecini[index].begin());
///cout<<" Vecin "<<vecinIndex<<"\n";
vecini[index].erase( remove(vecini[index].begin(), vecini[index].end(), vecinIndex), vecini[index].end());
vecini[vecinIndex].erase( remove(vecini[vecinIndex].begin(), vecini[vecinIndex].end(), index), vecini[vecinIndex].end());
find_min_level(vecinIndex, level+1);
if(v[vecinIndex].min_level < v[index].min_level){
v[index].min_level = v[vecinIndex].min_level;
v[index].min_father_index = v[vecinIndex].min_father_index;
}
}
///cout<<"-- up --\n";
}
int main()
{
input();
//afis_vecini();
find_min_level(1, 1);
//afis_noduri();
output();
return 0;
}