Pagini recente » Cod sursa (job #849791) | Cod sursa (job #1120886) | Cod sursa (job #2905939) | Cod sursa (job #892197) | Cod sursa (job #2059278)
#include<fstream>
#include<list>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100005;
list<int>g[NMAX];
stack<pair<int,int> >s;
vector<int>bcc[NMAX];
int link[NMAX],lowlink[NMAX],n,m,node_time,nr_bcc;
void read_data(){
int node1,node2;
fin>>n>>m;
while(m--){
fin>>node1>>node2;
g[node1].push_back(node2);
g[node2].push_back(node1);
}
}
void new_biconnected_component(int node1,int node2){
int bnode1,bnode2;
++nr_bcc;
do{
bnode1=s.top().first;
bnode2=s.top().second;
s.pop();
bcc[nr_bcc].push_back(bnode1);
bcc[nr_bcc].push_back(bnode2);
}while(bnode1!=node1 or bnode2!=node2);
}
void biconnected(int node){
link[node]=lowlink[node]=++node_time;
list<int>::iterator it;
for(it=g[node].begin();it!=g[node].end();++it)
if(!link[*it]){
s.push(make_pair(node,*it));
biconnected(*it);
lowlink[node]=min(lowlink[node],lowlink[*it]);
if(link[node]<=lowlink[*it])
new_biconnected_component(node,*it);
}
else
lowlink[node]=min(lowlink[node],link[*it]);
}
void print(){
vector<int>::iterator it;
int i;
fout<<nr_bcc<<'\n';
for(i=1;i<=nr_bcc;++i){
sort(bcc[i].begin(),bcc[i].end());
bcc[i].erase(unique(bcc[i].begin(),bcc[i].end()),bcc[i].end());
for(it=bcc[i].begin();it!=bcc[i].end();++it)
fout<<*it<<' ';
fout<<'\n';
}
}
int main(){
read_data();
biconnected(1);
print();
}