Cod sursa(job #3228518)

Utilizator VolterNikolay Volter Data 8 mai 2024 16:47:47
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.84 kb
#include <iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<unordered_set>
#include<unordered_map>
#include<fstream>

using namespace std;

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

long long times=0;
using ll=long long;
vector<vector<long long>> gr;
vector<long long> tim,fun;//tim - время входа в вершину а fun наим время возврата
vector<long long> col;//col - цвет или номер компоненты вершинной двусвязности
long long maxcolor=0;
vector<bool> painted;
map<pair<long long,long long>,vector<long long>> numedge;
vector<set<ll>> points;
set<long long> key;

void dfs(vector<bool> &used,ll v,ll p=-1){
    used[v]=1;
    tim[v]=times++;
    fun[v]=tim[v];
    int child=0;
    
    for (auto u:gr[v])
    {
        if(u==p){
        continue;
        }

        if(used[u]){
        fun[v]=min(fun[v],tim[u]);
        }

        else{
            dfs(used,u,v);
            fun[v]= min(fun[v],fun[u]);
            child++;

        }
 
    }

}



void paint(long long v,long long p=-1){
        painted[v]=1;
        
        for (auto u:gr[v])
        {
                if(u==p){
			//обратное ребро к родителю не нужно т.к оно ведет только вверх
                continue;
                }

                if(!painted[u]){
                
                        if(fun[u]>=tim[v]){
                            if(!key.empty())
                            points.push_back(key);

                            key=set<long long>();
                            //setColor(v,u,newcolor);
                            key.insert(u);
                            key.insert(v);
                            paint(u,v);
                        }else{
                            //тут нужно ребро vu
                            //setColor(v,u,color);
                            key.insert(u);
                            key.insert(v);
                            paint(u,v);
                        }
                
                }
                else if(tim[u]<tim[v])
                {
                    //setColor(v,u,color);
                    key.insert(u);
                    key.insert(v);
                }
        }
        
}

int main(){
        long long n,m;
        in>>n>>m;
        gr=vector<vector<long long>>(n);
        tim=vector<long long>(n);
        fun=vector<long long>(n);
        vector<bool> used= vector<bool>(n,0);

        painted=vector<bool>(n);
        col=vector<long long>(m);

        long long v,u;
        for (long long i = 0; i < m; i++)
        {
                in>>v>>u;
                --v;
                --u;
                gr[v].push_back(u);
                gr[u].push_back(v);

                numedge[make_pair(min(v,u),max(v,u))].push_back(i);
        }
        

        //Первый проход dfs для поиска точек сочленения
        for (long long v = 0; v < n; v++)
        {
                if(!used[v])
                dfs(used,v);
        }
        //Второй проход dfs для окраски графа по компононентам вершн двусвязности
        
        for (long long v = 0; v < n; v++)
        {
            if(!painted[v]){
                
                paint(v);
            }
        }
        if(!key.empty())
        points.push_back(key);

        out<<points.size()<<endl;
       
        for (auto i:points)
        {
            for (auto j:i)
            {
                out<<j+1<<" ";
                out.flush();
            }
            out<<endl;

        }
        
        
        
}