Cod sursa(job #2122487)

Utilizator alexandru822Bosinta Alexandru alexandru822 Data 5 februarie 2018 10:15:43
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

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


struct Pair
{
    int first, second;
};

const int N_MAX = 100050;
int neighbours[1 + N_MAX][1 + N_MAX/100];
vector<int> components[1 + N_MAX];
Pair dfs[2*N_MAX];
int n, k = 0, t= 0, depth[1 + N_MAX], height[1 + N_MAX], dad[1 + N_MAX], nrNb[1 + N_MAX];
bool visited[1 + N_MAX];

void read()
{
    int m;
    in >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        neighbours[x][nrNb[x]++] = y;
        neighbours[y][nrNb[y]++] = x;
    }
    depth[1] = 1;
    height[1] = 1;
}

void cache(int x, int y)
{
    vector<int> curcomp;
    int tx, ty;
    do
    {
        tx = dfs[k].first;
        ty = dfs[k].second;
        k--;
        curcomp.push_back(tx);
        curcomp.push_back(ty);
    }while(tx != x | ty != y);
    components[t] = curcomp;
    t++;
}

void DFS(int node)
{
    for(int i = 0; i < nrNb[node]; i++)
    {
        int m = neighbours[node][i];
        if(dad[node] == m)
            continue;
        if(depth[m])
            height[node] = min(height[node], height[m]);
        else
        {
            k++;
            dfs[k] = {node,m};
            dad[m] = node;
            depth[m] = depth[node] + 1;
            height[m] = depth[m];
            DFS(m);
            height[node] = min(height[node], height[m]);
            if(height[m] >= depth[node])
                cache(node, m);
        }
    }
}

void print()
{
    out << t << "\n";
    for(int m = 0; m < t; m++)
    {
        sort(components[m].begin(),components[m].end());
        auto it = unique(components[m].begin(),components[m].end());
        components[m].resize(distance(components[m].begin(),it));
        for(int r : components[m])
            out << r << " ";
        out << "\n";
    }
}

int main()
{
    read();
    DFS(1);
    print();
    return 0;
}