Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include<fstream>
- #include<algorithm>
- #include <stack>
- #define N 100005
- using namespace std;
- ifstream fin("componentebiconexe.in");
- ofstream fout("componentebiconexe.out");
- vector<int> G[N];
- vector< pair <int , int > >Mc;
- vector< vector<int > >biconex;
- int bcnt;
- bool nodc[N], viz[N];
- int low[N], level[N];
- stack<int> st;
- void DFS(int nd, int par, int rad)
- {
- viz[nd]=1;
- level[nd]=low[nd]=level[par]+1;
- st.push(nd);
- int sonCt=0;
- for(auto adj:G[nd])
- {
- if(adj==par) continue;
- if(viz[adj])
- {
- low[nd]=min(low[nd], level[adj]);
- continue;
- }
- ++sonCt;
- DFS(adj,nd, rad);
- ///muchii critica
- low[nd]=min(low[nd], low[adj]);
- if(level[nd]<low[adj])
- Mc.push_back(make_pair(nd,adj));
- ///biconex
- if(level[nd]<=low[adj])
- {
- ++bcnt;
- biconex.push_back(vector<int>(0));
- int x;
- do
- {
- x=st.top();
- st.pop();
- biconex[bcnt-1].push_back(x);
- }while(x!=adj);
- biconex[bcnt-1].push_back(nd);
- ///nod critic
- if(nd!=rad) nodc[nd]=1;
- }
- }
- }
- int main()
- {
- int cer;
- fin>>cer;
- int n,m,x,y;
- fin>>n>>m;
- for(int i=1;i<=m;i++)
- {
- fin>>x>>y;
- G[x].push_back(y);
- G[y].push_back(x);
- }
- for(int i=1;i<=n;i++)
- if(!viz[i]) DFS(i,0,i);
- if(cer==1)
- {
- fout<<bcnt<<"\n";
- for(int i=0;i<bcnt;i++)
- {
- fout<<biconex[i].size()<<" ";
- for(int j=0;j<biconex[i].size();j++)
- fout<<biconex[i][j]<<" ";
- fout<<"\n";
- }
- }
- else if(cer==2)
- {
- int cnt=0;
- for(int i=1;i<=n;i++)
- if(nodc[i])cnt++;
- fout<<cnt<<"\n";
- for(int i=1;i<=n;i++)
- if(nodc[i])fout<<i<<" ";
- }
- else{
- fout<<Mc.size()<<"\n";
- for(int i=0;i<Mc.size();i++)
- fout<<Mc[i].first<<" "<<Mc[i].second<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement