Cod sursa(job #854098)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 ianuarie 2013 20:09:01
Problema Componente biconexe Scor 58
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include<fstream>
#include<vector>
 
using namespace std;
 
 
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int urca[100001],nivel[100001];
vector <int> lv[100005];
vector <int> com[100005];
int nr;
vector <int> stack;
int cate,start;
void dfs(int nod,int niv,int tata)
{   int i;
    urca[nod]=niv;
    nivel[nod]=niv;
    stack.push_back(nod);
    for(i=0;i<lv[nod].size();i++)
    {
        if(!nivel[lv[nod][i]])
        { 
            stack.push_back(nod);
            dfs(lv[nod][i],niv+1,nod);
            if(urca[nod]>urca[lv[nod][i]])urca[nod]=urca[lv[nod][i]];
               else
                   if(urca[lv[nod][i]]>=niv)
                   {
                        int u,j=0;
                        u=stack.size()-1;
                        nr++;
                        while(stack[u]!=nod)
                        { 
                            if(!j||com[nr][j-1]!=stack[u])
                            { 
                                com[nr].push_back(stack[u--]);
                                j++;
                            }
                              else u--;     
                                                                   
                            stack.pop_back();
                        }
                        com[nr].push_back(stack[u]);
                        stack.pop_back();
                 
                                
                   }
        }
        else
            if(lv[nod][i]!=tata&&nivel[lv[nod][i]]<urca[nod]) urca[nod]=nivel[lv[nod][i]];
    } 
}
 
 
           
 
 
int n,m;
 
int main()
{
    int i;
     
    fin>>n;
    fin>>m;
     
    for(i=1;i<=m;i++)
    {   
        int x,y;
        fin>>x>>y;
        lv[x].push_back(y);
        lv[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!nivel[i])dfs(i,1,0);
     
    fout<<nr<<"\n";
    for(i=1;i<=nr;i++)
    {
        int j,k;
        k=com[i].size();
        for(j=0;j<k;j++)
            fout<<com[i][j]<<" ";
        fout<<"\n";
    }
        
}