Cod sursa(job #2355411)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 26 februarie 2019 08:31:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

FILE *f = fopen("biconex.in","r");
FILE *g = fopen("biconex.out","w");

const int NMAX = 1e5;
const int MMAX = 2e5;


int n,m;
vector<int> graph[NMAX + 5];

int id[NMAX + 5];
int low[NMAX + 5];
int last_id;
pair<int,int> st[MMAX + 5];
int len;

vector< vector<int> > bicco;

void dfs(int nod,int tata){
    low[nod] = id[nod] = ++last_id;

    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }

        if(id[it]){
            low[nod] = min(low[nod],id[it]);
        }
        else{
            st[++len] = {it,nod};
            dfs(it,nod);
            low[nod] = min(low[nod],low[it]);
            if(low[it] >= id[nod]){
                vector<int> v;
                while(st[len] != make_pair(it,nod)){
                    v.push_back(st[len].first);
                    v.push_back(st[len].second);
                    len--;
                }
                v.push_back(st[len].first);
                v.push_back(st[len].second);
                len--;

                sort(v.begin(),v.end());
                v.resize(unique(v.begin(),v.end()) - v.begin());
                bicco.push_back(v);
            }
        }
    }
}

int main(){

    fscanf(f,"%d %d",&n,&m);

    for(int i = 1;i <= m;i++){
        int x,y;
        fscanf(f,"%d %d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(1,0);

    fprintf(g,"%d\n",(int)bicco.size());

    for(auto it:bicco){
        for(auto it2:it){
            fprintf(g,"%d ",it2);
        }
        fprintf(g,"\n");
    }

    return 0;
}