Cod sursa(job #2128966)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 12 februarie 2018 12:51:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#define DIM 100002
#define f first
#define s second

using namespace std;

ifstream in ("biconex.in");
ofstream out("biconex.out");

int n, m, x, y, art[DIM], viz[DIM], nivmin[DIM], lvl[DIM], p;

vector <int> graf[DIM], pctCrit;
vector <vector<int> > cc;
deque <pair<int, int> > q;

void make_cc(int x, int y){
    vector <int> v;
    while(q.back().f != x || q.back().s != y){
        v.push_back(q.back().f);
        v.push_back(q.back().s);
        q.pop_back();
    }
    v.push_back(x);
    v.push_back(y);
    q.pop_back();
    cc.push_back(v);
}

void dfs(int nod, int tata, int niv){
    viz[nod] = 1;
    nivmin[nod] = niv;
    lvl[nod] = niv;
    for(int i = 0; i < graf[nod].size(); ++ i){
        int nodc = graf[nod][i];
        if(nodc == tata)
            continue;
        if(!viz[nodc]){
            q.push_back(make_pair(nod, nodc));
            dfs(nodc, nod, niv + 1);
            nivmin[nod] = min(nivmin[nodc], nivmin[nod]);
            if(nivmin[nodc] >= lvl[nod]){
                make_cc(nod, nodc);
            }
            
        }
        else
            nivmin[nod] = min(nivmin[nod], lvl[nodc]);
    }
    if(nod == 1 && graf[1].size() > 1)
        pctCrit.push_back(1);
    if(nod != 1)
    for(int i = 0; i < graf[nod].size(); ++ i){
        if(nivmin[graf[nod][i]] >= lvl[nod]){
            pctCrit.push_back(nod);
            break;
        }
    }
}

int main() {
    p = 1;
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    dfs(1, 0, 0);
    if(p == 1){
        out<<cc.size()<<'\n';
        for(int i = 0; i < cc.size(); ++ i){
            sort(cc[i].begin(), cc[i].end());
            cc[i].erase(unique(cc[i].begin(), cc[i].end()), cc[i].end());
           // out<<cc[i].size()<<" ";
            for(int j = 0; j < cc[i].size(); ++ j){
                out<<cc[i][j]<<" ";
            }
            out<<'\n';
        }
    }
    if(p == 2){
        out<<pctCrit.size()<<'\n';
        for(vector<int> :: iterator it = pctCrit.begin(); it != pctCrit.end(); ++ it)
            out<<*it<<' ';
    }
    return 0;
}