Cod sursa(job #1967834)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 17 aprilie 2017 09:47:07
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.66 kb
#include<cstdio>
#include<vector>

using namespace std;

const int NMAX = 100000;

int n,m;
vector<int> adj[1 + NMAX];
vector<int> vertex[1 + NMAX];
int vertex_used[1 + 2 * NMAX];
int level[1 + NMAX];
int level_min[1 + NMAX];
struct str
{
    int l,r;
} stk[1 + 3 * NMAX];
int top;
vector<int> res[1 + NMAX];
int res_ct;

int mi(int a, int b)
{
    if(a < b)
    {
        return a;
    }
    return b;
}

void solve(int node, int lvl)
{
    level[node] = lvl;
    level_min[node] = lvl;

    vector<int>::iterator it = adj[node].begin();
    vector<int>::iterator it2 = vertex[node].begin();

    while(it != adj[node].end())
    {
        if(vertex_used[*it2] == 0)
        {
            vertex_used[*it2] = 1;
            /*printf("* %d %d %d\n",node, level[node], level_min[node]);
            for(int i = 1; i <= top; i++)
            {
                printf("%d %d\n", stk[i].l, stk[i].r);
            }
            printf("\n");*/

            if(level[*it] == 0)
            {
                top++;
                stk[top].l = node;
                stk[top].r = *it;
                solve(*it, lvl + 1);
            }
            level_min[node] = min(level_min[node], level_min[*it]);

            if(level[node] <= level_min[*it])
            {
                res_ct++;
                do
                {
                    res[res_ct].push_back(stk[top].r);
                    if(stk[top].l == node && stk[top].r == *it)
                    {
                        res[res_ct].push_back(stk[top].l);
                        top--;
                        break;
                    }
                    top--;
                } while(1);
            }
        }
        it++;
        it2++;
    }
    /*printf("%d %d %d\n",node, level[node], level_min[node]);
    printf("\n");*/
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        level_min[i] = 1000000000;
    }

    int x,y;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);

        adj[x].push_back(y);
        adj[y].push_back(x);
        vertex[x].push_back(i);
        vertex[y].push_back(i);
    }

    solve(1, 1);

    /*for(int i = 1; i <= n; i++)
    {
        printf("%d %d %d\n", i, level[i], level_min[i]);
    }
    printf("\n");*/

    printf("%d\n",res_ct);
    for(int i = 1; i <= res_ct; i++)
    {
        for(vector<int>::iterator it = res[i].begin(); it != res[i].end(); it++)
        {
            printf("%d ", *it);
        }
        printf("\n");
    }
}