Cod sursa(job #1384586)

Utilizator devilz05Orzan Alexandru devilz05 Data 11 martie 2015 11:06:55
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>

#define MAX 200000

using namespace std;

int lowest[MAX], dist[MAX];
stack<pair<int, int> > edges;
vector<list<int> > graph;
vector<vector<int> > sol;

void read()
{
    ifstream f("biconex.in");
    int i, j;
    
    f >> i >> j;
    graph.resize(i+1);
    while (f >> i && f >> j)
    {
        graph[i].push_back(j);
        graph[j].push_back(i);
    }
    f.close();
}

void DFS(int node, int parent)
{
    lowest[node] = dist[node] = dist[parent] + 1;
    for (list<int>::iterator i = graph[node].begin(); i != graph[node].end(); ++i)
    {
        int adj = *i;
        if (adj == parent) continue;
        
        if (dist[adj] == -1)
        {
            edges.push(make_pair(node, adj));
            DFS(adj, node);
            lowest[node] = min(lowest[node], lowest[adj]);
            if (lowest[adj] >= dist[node])
            {
                vector<int> solVector;
                while (!edges.empty())
                {
                    solVector.push_back(edges.top().first);
                    solVector.push_back(edges.top().second);
                    
                    if (edges.top().first == node && edges.top().second == adj)
                    {
                        edges.pop();
                        break;
                    }
                    edges.pop();
                }
                
                sort(solVector.begin(), solVector.end());
                for (vector<int>::iterator j = solVector.begin(); j != solVector.end() - 1; ++j)
                {
                    if (*j == *(j+1))
                    {
                        solVector.erase(j);
                        --j;
                    }
                }
                sol.push_back(solVector);
            }
        }
        else
            lowest[node] = min(lowest[node], lowest[adj]);
    }
}

void write()
{
    ofstream f("biconex.out");
    
    f << sol.size() << "\n";
    for (vector<vector<int> >::iterator i = sol.begin(); i != sol.end(); ++i)
    {
        for (vector<int>::iterator j = i->begin(); j != i->end(); ++j)
            f << *j << " ";
        f << "\n";
    }
    
    f.close();
}

int main()
{
    read();
    
    for (int i = 0; i < MAX; ++i) dist[i] = -1;
    DFS(1, 0);
    write();
    
    return 0;
}