Cod sursa(job #1259989)

Utilizator Tester100Tester Tester100 Data 10 noiembrie 2014 19:31:06
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <vector>
#include <stack>
#define pii pair < int ,int >
#define fi first
#define se second
using namespace std;
const int NMAX = 100004;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack < pii > St;
vector < int > Graph[NMAX];
vector < vector < pii > > sol;
int level[NMAX] , low[NMAX], Root, use[NMAX];
inline void Read(){
    int n, m;
    f >> n >> m;
    for(int i=1;i<=m;++i){
        int x, y;
        f >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }
    f.close();
}
inline vector < pii > Solve(const pii a){
    vector < pii > ret;
    while(St.top()!=a)
    {
        ret.push_back(St.top());
        St.pop();
    }
    ret.push_back(a);
    St.pop();
    return ret;
}
inline void DFS(const int node,const int Father,const int niv){
    int cnt = 0;
    level[node] = niv;
    low[node] = niv;
    for(vector < int >::iterator it = Graph[node].begin(); it != Graph[node].end(); ++it){
        int x = *it;
        if(x==Father)
            continue;
        if(level[x]==0){
            St.push(make_pair(node,x));
            DFS(x,node,niv+1);
            low[node] = min(low[node],low[x]);
            if(low[x] >= niv){
                sol.push_back(Solve(make_pair(node,x)));
            }
            ++cnt;
        }
        else
            low[node] = min(low[node],level[x]);
    }
    if(cnt==0)
        return ;
}
inline vector < int >  Decodif(vector < pii > v){
    vector < int >ret;
    for(unsigned i = 0;i < v.size(); ++i){
        if(!use[v[i].fi]){
            ret.push_back(v[i].fi);
            use[v[i].fi] = 1;
        }
        if(!use[v[i].se]){
            ret.push_back(v[i].se);
            use[v[i].se] = 1;
        }
    }
    for(unsigned i = 0;i < ret.size(); ++i)
        use[ret[i]] = 0;
    return ret;
}

inline void Write(){
    g<<sol.size()<<"\n";
    for(unsigned i = 0;i < sol.size(); ++i){
        vector < int > v = Decodif(sol[i]);
        for(unsigned j = 0;j < v.size(); ++j)
            g<<v[j]<<" ";
        g<<"\n";
    }
    g.close();
}
int main()
{
    Read();
    Root = 1;
    DFS(1,0,1);
    Write();
    return 0;
}