Cod sursa(job #1027243)

Utilizator lucianRRuscanu Lucian lucianR Data 12 noiembrie 2013 17:18:42
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#define N_MAX 100001

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");

vector <int> v[N_MAX];
bool visited[N_MAX];
int cc = 0, N, M, pre[N_MAX], comp[20000][2000], end[N_MAX], art[N_MAX], na;

void DFS(int node)
{
    bool check = 1;
    for(int i = 0; i < v[node].size(); i++)
    {
        //cout<<i<<endl;
        if(visited[v[node][i]] && v[node][i] != pre[node] && !end[v[node][i]])
        {
            art[na++] = v[node][i];
            //pre[v[node][i]] = node;
        }
        if(!visited[v[node][i]])
        {
            check = 0;
            visited[v[node][i]] = true;
            pre[v[node][i]] = node;
            DFS(v[node][i]);
        }
    }
    if(check == 1) end[node] = 1;
}

void DFSc(int node)
{
    for(int i = 0; i < v[node].size(); i++)
    {
        //cout<<"NODE"<<node<<" "<<v[node][i];
        if(!visited[v[node][i]] /*&& v[node][i] != art[na]*/)
        {
            visited[v[node][i]] = true;
            out << v[node][i] << " ";
            if(v[node][i] != art[na]) DFSc(v[node][i]);
        }
        if(v[node][i] == art[na] && pre[node] != v[node][i])
        {
            //cout<<"OF"<<art[na];
            na++;
            out <<"\n"<<art[na-1]<<" ";
            DFSc(art[na-1]);
        }
    }
}

int main()
{
    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    visited[1] = true;
    DFS(1);
    for(int i = 1; i <= N; i++)
    {
        visited[i] = 0;
    }
    out << na + 1 << "\n";
    na = 0;
    visited[art[na]] = 1;
    out << art[na] << " ";
    DFSc(art[na]);
    return 0;
}