Cod sursa(job #2143360)

Utilizator sulzandreiandrei sulzandrei Data 25 februarie 2018 21:00:58
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_set>
#include <stack>
#define min(a,b) ((a<b)?a:b)//folosesc macroul pt. cai mai rapid decat o functie
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct ele
{
    int x,y;
}edge;
vector< unordered_set<int>> ms;
bitset<100003> viz;
stack <struct ele> s;
vector<int> niv,nic,v[100003];
int nr=0,start;
void DFS(int i)
{
    for(const int& j:v[i])
    {
        if(viz[j]==0)
        {
            edge.x = i;
            edge.y = j;
            s.push(edge);
            viz[j] = 1;
            niv[j]=niv[i]+1; nic[j]=niv[j];
            DFS(j);
            nic[i]=min(nic[j],nic[i]);
            if (nic[j]>=niv[i])
            {
                unordered_set<int> mse;
                do
                {
                    edge = s.top();
                    s.pop();
                    if(mse.find(edge.x) == mse.end())
                        mse.insert(edge.x);
                    if(mse.find(edge.y) == mse.end())
                        mse.insert(edge.y);
                }
                while(edge.x!=i || edge.y!= j);
                ms.push_back(mse);
                mse.clear();
                nr++;
            }
        }
        else
            if (niv[j]<nic[i] && niv[j]!=niv[i]-1)
                nic[i] = niv[j];
    }
}
int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    nic.resize(n+1);
    niv.resize(n+1);
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    start = 1;
    niv[start]= nic[start]= viz[start]=1;
    DFS(start);
    out<<nr<<"\n";
    for(i=0;i<nr;i++)
    {
        for(const int& e :ms[i])
            out<<e<<" ";
        out<<"\n";
    }
    return 0;
}