Cod sursa(job #1225423)

Utilizator smaraldaSmaranda Dinu smaralda Data 2 septembrie 2014 16:00:27
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;

const int INF = 2e9, NMAX = 1e5;

struct EDGE { int node, ind; };

vector <EDGE> graph[NMAX + 5];
vector <int> comp[NMAX +5];
int a[2 * NMAX + 5], b[2 * NMAX + 5], vis[NMAX + 5], critic[2 * NMAX + 5], level[NMAX + 5], dp[NMAX + 5], dad[NMAX + 5];

int n,lvl,cnt,res;

void dfs (int node, int edge) {
    vector <EDGE>::iterator it;
    vis[node] = 1;
    dp[node] = INF;
    level[node] = ++ lvl;
    for(it = graph[node].begin(); it != graph[node].end(); it++)
        if(!vis[it -> node]) {
            dad[it -> node] = node;
            dfs(it -> node, it -> ind);
            dp[node] = min(dp[node], dp[it -> node]);
            }
        else
            if(it -> node != dad[node])
                dp[node] = min(dp[node], level[it -> node]);
    if(dp[node] >= level[node])
        critic[edge] = 1;
    -- lvl;
}

void dfs2 (int node) {
    vector <EDGE>::iterator it;
    vis[node] = cnt;
    comp[cnt].push_back(node);
    for(it = graph[node].begin(); it != graph[node].end(); it++)
        if(!critic[it -> ind] && !vis[it -> node])
            dfs2(it -> node);
}

int main() {
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int m,i;
    vector <int>::iterator it;

    scanf("%d%d",&n,&m);
    for(i = 1; i <= m; i++) {
        scanf("%d%d",&a[i],&b[i]);
        graph[a[i]].push_back({b[i],i});
        graph[b[i]].push_back({a[i],i});
        }

    lvl = 0;
    for(i = 1; i <= n; i++)
        if(!vis[i])
            dfs(i, 0);

    memset(vis, 0, sizeof(vis));
    for(i = 1; i <= n; i++)
        if(!vis[i]) {
            ++ cnt;
            dfs2(i);
            }

    for(i = 1; i <= m; i++)
        if(critic[i]) {
            ++cnt;
            comp[cnt].push_back(a[i]);
            comp[cnt].push_back(b[i]);
            }

   /* res = cnt;
    for(i = 1; i <= cnt; i++)
        if(comp[i].size() < 2)
            res--;*/

    printf("%d\n",res);
    for(i = 1; i <= cnt; i++)
        if(comp[i].size() > 1) {
            for(it = comp[i].begin(); it != comp[i].end(); it++)
                printf("%d ",*it);
            printf("\n");
            }
    return 0;
}