Cod sursa(job #1733392)

Utilizator mirupetPetcan Miruna mirupet Data 24 iulie 2016 16:54:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <vector>
#include <stack>
#define Minim(x, y) (x <= y ? x : y)
#define NMax 100005
using namespace std;

FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

int N, M, cnt;
int w[NMax], mini[NMax];
vector < int > sol[NMax], v[NMax];
stack < pair < int, int > > st;

void DFS(int node, int father)
{
    w[node] = mini[node] = w[father] + 1;

    for (int i = 0; i < v[node].size(); i++)
        if (v[node][i] != father)
        {
            if (!w[ v[node][i] ])
            {
                st.push(make_pair(node, v[node][i]));
                DFS(v[node][i], node);
                if (mini[ v[node][i] ] >= w[node])
                {
                    int a = 0, b = 0;
                    cnt ++;
                    while (a != node && b != v[node][i])
                    {
                        a = st.top().first;
                        b = st.top().second;
                        st.pop();
                        sol[cnt].push_back(b);
                    }
                    sol[cnt].push_back(node);
                }
            }
            mini[node] = Minim(mini[node], mini[ v[node][i] ]);
        }
}
int main()
    {
        scanf("%d%d", &N, &M);

        for (int i = 1, X, Y; i <= M; i++)
        {
            scanf("%d%d", &X, &Y);
            v[X].push_back(Y);
            v[Y].push_back(X);
        }

        DFS(1, 0);

        printf("%d\n", cnt);

        for (int i = 1; i <= cnt; i++, printf("\n"))
        {
            for (int j = 0; j < sol[i].size(); j++)
                printf("%d ", sol[i][j]);
        }
    }