Cod sursa(job #2003419)

Utilizator infomaxInfomax infomax Data 22 iulie 2017 21:08:17
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

FILE *F=fopen("biconex.in", "r"), *G=fopen("biconex.out", "w");

int kb, n, m, x, y, l[100003], w[100003];
///bitset<100003> w;
vector<int> c[100003], a[100003];
vector<int> :: iterator it1;
stack<pair<int, int> > st;

void scot_stiva(int x, int y)
{
    int a, b;
    ++ kb;
    do
    {
        a = st.top().f;
        b = st.top().s;
        st.pop();
        c[kb].push_back(a);
        c[kb].push_back(b);
    }while(a!=x && b!=y);
}

void dfs(int nod, int t, int nr)
{
    vector<int> :: iterator it;
    w[nod] = l[nod] = nr;
    for(it = a[nod].begin(); it != a[nod].end(); ++ it)
    {
        x = *it;
        if(*it == t) continue;
        if(w[*it] == -1)
        {
            st.push({nod, *it});
            dfs(*it, nod, nr+1);
            l[nod] = min(l[nod], l[*it]);
            if(l[*it] >= w[nod])
                scot_stiva(nod, *it);
        }
        else l[nod] = w[*it];
    }
}

int main()
{
    fscanf(F, "%d%d ", &n, &m);
    for(int i = 1; i <= m; ++ i)
    {
        fscanf(F, "%d%d ", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i = 1; i <= n; ++ i) w[i] = -1;
    dfs(1, 0, 0);
    fprintf(G, "%d\n", kb);
    for(int i = 1; i <= kb; ++ i, fputc('\n', G))
    {
        sort(c[i].begin(), c[i].end());
        c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
        for(it1 = c[i].begin(); it1 != c[i].end(); ++ it1)
            fprintf(G, "%d ", *it1);
    }
    return 0;
}