Cod sursa(job #1858488)

Utilizator serbanSlincu Serban serban Data 27 ianuarie 2017 15:25:42
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> G[1000005];
vector< pair<int, int> > M;

int viz[100005];

vector<int> v;

vector< vector<int> > ans;

int fi, se;

void df(int x, int prec) {

    viz[x] = 2;
    for(int j = 0; j < G[x].size(); j ++) {

        if(G[x][j] != prec) {
            int lucky = viz[ G[x][j] ];

            if(!lucky) {
                df(G[x][j], x);
                viz[x] = min(viz[x], viz[ G[x][j] ]);
            }
            else if(lucky == 1) viz[x] = 1;
        }
    }
}


int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    int n, m;
    f >> n >> m;

    int x, y;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        M.push_back( {x, y} );
    }

    for(int i = 0; i < m; i ++) {

        viz[ M[i].first ] = 1;
        viz[ M[i].second ] = 1;

        fi = M[i].first;
        se = M[i].second;

        df(se, fi);

        viz[ M[i].first ] = 1;
        viz[ M[i].second ] = 1;

        df(fi, se);

        viz[ M[i].first ] = 1;
        viz[ M[i].second ] = 1;

        bool exista = false;

        int kkt = 0;
        for(int j = 1; j <= n; j ++)
            if(viz[j] == 1) {
                kkt ++;
            }
            if(kkt == 2)
                exista = true;


        if(exista) {
            v.push_back(fi);
            v.push_back(se);

            for(int j = 1; j <= n; j ++)
                viz[j] = 0;
        }
        else {
            for(int j = 1; j <= n; j ++) {
                if(viz[j] == 1) v.push_back(j);
                viz[j] = 0;
            }
        }


        ans.push_back(v);
        v.clear();
    }

    sort(ans.begin(), ans.end());

    for(int i = 1; i < ans.size(); i ++) {
        if(ans[i] == ans[i - 1]) {
            for(int j = i; j < ans.size() - 1; j ++)
                ans[j] = ans[j + 1];
            ans.pop_back();
            i --;
        }
    }
    g << ans.size() << "\n";

    for(int i = 0; i < ans.size(); i ++) {
        for(int j = 0; j < ans[i].size(); j ++)
            g << ans[i][j] << " ";
        g << "\n";
    }

    return 0;
}