Cod sursa(job #1392058)

Utilizator misinozzz zzz misino Data 18 martie 2015 12:45:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<vector>
#include<algorithm>

#define N 100100

using namespace std;

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

int n,m,i,x,y,j,nr,viz[N],mini[N],niv[N];

vector<int>v[N],s[N];
vector<pair<int,int> >vec;

inline void adauga(int x, int y){
    s[++nr].push_back(x);
    s[nr].push_back(y);

    while(!vec.empty() && !(vec.back().first == x && vec.back().second == y || (vec.back().first == y && vec.back().second == x)))
    {
        s[nr].push_back(vec.back().first);
        s[nr].push_back(vec.back().second);
        vec.pop_back();
    }
    vec.pop_back();
}

inline void dfs(int x,int t){
    viz[x] = 1;

    for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if(!viz[*it])
        {
            mini[*it] = niv[*it] = niv[x] + 1;
            vec.push_back(make_pair(x, *it));

            dfs(*it, x);

            mini[x] = min(mini[x], mini[*it]);

            if(mini[*it] >= niv[x])
                adauga(x, *it);
        }
        else
            if(*it != t)
                mini[x] = min(niv[*it], mini[x]);
}

int main()
{
    f >> n >> m;

    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    g << nr << '\n';

    for(i = 1; i <= nr; ++i)
    {
        sort(s[i].begin(),s[i].end());
         g << s[i][0] << ' ';
        for(j = 1; j < s[i].size(); ++j)
            if(s[i][j] != s[i][j - 1])
                g << s[i][j] << ' ';
        g << '\n';
    }

    return 0;
}