Cod sursa(job #1830507)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 16 decembrie 2016 20:02:09
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
FILE *f=fopen("biconex.in","r");
vector <int> lv[200009],lf[200009];
int ni[200009],sus[200009];
stack <int> s;
int n,m,used[200009];
void citire( )
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
         fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
        lv[y].push_back(x);
    }
}
int k=0,p=0;
void dfs(int nc,int t)
{
    used[nc]=1;
    ni[nc] = ni[t]+1;
    sus[nc] = ni[nc];
    vector <int> ::iterator ii;
    s.push(nc);
    for(ii=lv[nc].begin();ii!=lv[nc].end();ii++)
    {
        if(t==*ii)
             continue ;
        if(!used[*ii])
           {

               dfs(*ii,nc);
               sus[nc]=min(sus[nc],sus[*ii]);
                 if(ni[nc]<=sus[*ii])
                {
                     k++;

                    while(s.top( )!=nc)
                    {
                        lf[k].push_back(s.top());
                        s.pop();
                    }
                   lf[k].push_back(nc);


                }
           }
        else
        {
            sus[nc]=min(sus[nc],sus[*ii]);


        }
    }
}
int main()
{
    citire( );
    dfs(1,0);
    FILE *f=fopen("biconex.out","w");
    for(int i=1;i<=n;i++)
        if(!used[i])
           dfs(i,0);
    fprintf(f,"%d\n",k);


      vector <int> ::iterator ii;
     for(int i=1;i<=k;i++)
         {for(ii=lf[i].begin();ii!=lf[i].end();ii++)
             fprintf(f,"%d ",*ii);
       fprintf(f,"\n");
       }
    return 0;
}