Cod sursa(job #2172123)

Utilizator Garen456Paun Tudor Garen456 Data 15 martie 2018 15:09:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector<int>V[100005];
int df[100005],bf[100005];

vector <vector <int> > C;

stack <pair <int, int> > stk;


void solve(int x,int y)
{
    vector <int> cm; int tx,ty;

    do
    { tx= stk.top().first, ty=stk.top().second; stk.pop();
      cm.push_back(tx); cm.push_back(ty);
    }
    while(tx!=x || ty!=y );
    C.push_back(cm);
}

void DFS(int son,int dad, int len)
{
    df[son]=bf[son]=len;
    vector<int>::iterator it;

    for(it=V[son].begin();it!=V[son].end();++it)
    { if(*it==dad) continue;
        if(df[*it]==0)
        {    stk.push( make_pair(son,*it)  );
            DFS(*it,son,len+1);
            bf[son]=min( bf[*it],bf[son]);
            if( bf[*it] >= df[son] )
                solve(son,*it);
        }

       else bf[son]=min(bf[son],df[*it]);

    }

}



int main()
{
    fin>>n>>m;
    int i,x,y,j;
    for(i=1;i<=m;++i)
    { fin>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    DFS(1,0,1);
     fout<<C.size()<<"\n";
     for(i=0;i<C.size();++i)
     { sort(C[i].begin(),C[i].end());
         C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
          for ( j = 0; j < C[i].size(); ++ j)
            fout << C[i][j] << " ";
        fout << "\n";
     }
    return 0;
}