Cod sursa(job #3374298)

Utilizator Moriiandrei Morii Data 8 noiembrie 2026 22:16:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
//#define int long long
using namespace std;


int tin[100001];
vector<int>M[100001];
int low[100001];
int timp ;
int n,m;
vector<set<int>>ans;
stack<pair<int,int>>ss;


void dfs(int nod,int tata)
   {
        timp++;
        tin[nod] = low[nod] = timp;
        for(auto i : M[nod])
          {
               if(i == tata)
                  continue;

             if(tin[i]){
                low[nod] = min(low[nod],tin[i]);

                if(tin[i] < tin[nod])
                     {
                         ss.push({nod,i});

                     }

              }
                else{
                        ss.push({nod,i});

                     dfs(i,nod);
                     low[nod] = min(low[nod],low[i]);
              if(low[i]>=tin[nod])
                {
                     set<int>temp;
                     while(1)
                        {
                            pair<int,int>pp = ss.top();
                            ss.pop();
                            int st = pp.first,dr = pp.second;
                            temp.insert(st),temp.insert(dr);
                            if(st == nod && dr == i)
                                break;



                        }
                        ans.push_back(temp);




                }


                }



          }





   }





signed main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);

             timp =0;
              cin >> n >> m;
              for(int i = 1;i<m+1;++i)
               {
                   int a,b;
                   cin >> a >> b;
                   M[a].push_back(b),M[b].push_back(a);

               }
            for(int i = 1;i<=n;++i)
             if(!tin[i ])
            dfs(i,0);


          cout << ans.size() << endl;
          for(int i = 0;i<ans.size();++i)
                {
                    for(auto j : ans[i])
                        cout << j << " ";

                    cout << endl;
                }












    return 0;
}