Cod sursa(job #3136121)

Utilizator NashikAndrei Feodorov Nashik Data 5 iunie 2023 14:41:10
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 11.4 kb
/*
 * Graph struct
 */
//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("biconexe.in");
ofstream cout("biconexe.out");
int is_artic[100005];
vector <int> sol[100005];
int contor=0;
struct Graph{
    ///consider graph has node from 1 to node
    const int INF=1000000000;
    struct Edge{
        ///struct for edges
        int u,v,w;
        Edge(int u,int v,int w){
            this->u=u;
            this->v=v;
            this->w=w;
        }
        Edge(int u,int v){
            this->u=u;
            this->v=v;
            this->w=1;
        }
    };
    struct Corr_Edge{
        ///struct for the correspondent node and weight for a certain edge
        int v,w;
        Corr_Edge(int v,int w){
            this->v=v;
            this->w=w;
        }
        Corr_Edge(int v) {
            this->v = v;
            this->w = 1;
        }
    };
    int nodes,edges,nr_conexe;
    bool NEG_CYCLE=false;
    vector <Edge> edge_set;
    vector <int> in_deg;
    vector <int> out_deg;
    vector <int> bfs_cost;
    vector <int> dijkstra_cost;
    vector <int> spfa_cost;
    vector <int> topo;
    vector <vector <int> > royfloyd_cost;
    vector <int> connected_component;
    vector <vector<int> > same_component;
    vector <int> dfs_order;
    vector <int> tata_art;
    vector <vector<int> > copii_art;
    vector <int> low;

    int contor_art;
    vector <vector<Corr_Edge > >adjacency_list;
    Graph(int nodes){
        this->nodes=nodes;
        this->edges=0;
        for(int i=0;i<=nodes;i++){
            vector <Corr_Edge > v;
            adjacency_list.push_back(v);
            in_deg.push_back(0);
            out_deg.push_back(0);
        }
    }
    ///add edges to graph
    void do_Deg(int u,int v){
        out_deg[u]++;
        in_deg[v]++;
    }
    void add_UEdge(int u,int v,int w){
        edge_set.push_back(Edge(u,v,w));
        do_Deg(u,v);
        do_Deg(v,u);
        adjacency_list[u].push_back(Corr_Edge(v,w));
        adjacency_list[v].push_back(Corr_Edge(u,w));
    }
    void add_UEdge(int u,int v){
        edge_set.push_back(Edge(u,v));
        do_Deg(u,v);
        do_Deg(v,u);
        adjacency_list[u].push_back(Corr_Edge(v,1));
        adjacency_list[v].push_back(Corr_Edge(u,1));
    }
    void add_DEdge(int u,int v,int w){
        do_Deg(u,v);
        edge_set.push_back(Edge(u,v,w));
        adjacency_list[u].push_back(Corr_Edge(v,w));
    }
    void add_DEdge(int u,int v){
        do_Deg(u,v);
        edge_set.push_back(Edge(u,v));
        adjacency_list[u].push_back(Corr_Edge(v,1));
    }

    ///bfs
    void bfs(int source){
        vector <int> s;
        s.push_back(source);
        bfs(s);
    }
    void bfs(vector <int> source){
        if(bfs_cost.size()==0){
            for(int i=0;i<=nodes;i++){
                bfs_cost.push_back(-1);
            }
        }
        fill(bfs_cost.begin(),bfs_cost.end(),-1);
        queue <pair<int,int> >q;

        for(auto u:source) {
            q.push(make_pair(u, 0));
            bfs_cost[u]=0;
        }
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            int curr=u.first,curr_cost=u.second;
            for(auto uu:adjacency_list[curr]){
                if(bfs_cost[uu.v]==-1){
                    bfs_cost[uu.v]=curr_cost+1;
                    q.push(make_pair(uu.v,curr_cost+1));
                }
            }
        }
    }
    int bfs_distance(int nod){
        return bfs_cost[nod];
    }

    ///connected_components
    void dfs_colour(int nod,int colour){
        connected_component[nod]=colour;
        same_component[colour].push_back(nod);
        for(auto u:adjacency_list[nod]){
            if(connected_component[u.v]==-1){
                dfs_colour(u.v,colour);
            }
        }
    }
    void components(){
        if(connected_component.size()==0){
            vector <int> v;
            for(int i=0;i<=nodes;i++){
                connected_component.push_back(-1);
                same_component.push_back(v);
            }
        }else
        fill(connected_component.begin(),connected_component.end(),-1);
        nr_conexe=0;
        for(int i=1;i<=nodes;i++){
            if(connected_component[i]==-1){
                nr_conexe++;
                connected_component[i]=nr_conexe;
                dfs_colour(i,nr_conexe);
            }
        }
    }
    int nr_components(){
        return nr_conexe;
    }
    vector <int> component(int node){
        return same_component[connected_component[node]];
    }

    ///dijkstra
    void dijkstra(int source){
        vector <int> v;
        v.push_back(source);
        dijkstra(v);
    }
    void dijkstra(vector <int> source){
        if(dijkstra_cost.size()==0){
            for(int i=0;i<=nodes;i++) {
                dijkstra_cost.push_back(-1);
            }
        }
        else
            fill(dijkstra_cost.begin(),dijkstra_cost.end(),-1);
        priority_queue <pair<int,int> >pq;
        for(auto u:source){
            pq.push(make_pair(0,u));
        }
        while(!pq.empty()){
            auto u=pq.top();
            pq.pop();
            int nod=u.second;
            int cost=-u.first;
            if(dijkstra_cost[nod]!=-1)
                continue;
            dijkstra_cost[nod]=cost;
            for(auto u:adjacency_list[nod]){
                if(dijkstra_cost[u.v]==-1){
                    pq.push(make_pair(-(cost+u.w),u.v));
                }
            }
        }
    }
    int dijkstra_distance(int nod){
        return dijkstra_cost[nod];
    }

    ///spfa
    void spfa(int source){
        vector <int> v;
        v.push_back(source);
        spfa(v);
    }
    void spfa(vector <int> source){
        if(spfa_cost.size()==0){
            for(int i=0;i<=nodes;i++)
            spfa_cost.push_back(INF);
        }
        else{
            fill(spfa_cost.begin(),spfa_cost.end(),INF);
        }
        queue <int> q;
        bool inside[nodes+2];
        int viz[nodes+2];
        for(int i=0;i<=nodes;i++){
            inside[i]=false;
            viz[i]=0;
        }
        for(auto u:source){
            spfa_cost[u]=0;
            q.push(u);
            inside[u]=true;
        }
        while(!q.empty()){
            int nod=q.front();
            q.pop();
            inside[nod]=false;
            viz[nod]++;
            if(viz[nod]==nodes){
                ///negative cycle
                NEG_CYCLE=true;
                return;
            }
            for(auto u:adjacency_list[nod]){
                if(spfa_cost[u.v]>spfa_cost[nod]+u.w){
                    spfa_cost[u.v]=spfa_cost[nod]+u.w;
                    if(!inside[u.v]){
                        inside[u.v]=true;
                        q.push(u.v);
                    }
                }
            }
        }
    }
    int spfa_distance(int nod){
        return spfa_cost[nod];
    }

    ///royfloyd
    void royfloyd() {
        if (royfloyd_cost.size() == 0) {
            vector<int> v;
            for (int i = 0; i <= nodes; i++)
                v.push_back(INF);
            for (int i = 0; i <= nodes; i++) {
                royfloyd_cost.push_back(v);
            }
        } else {
            for(int i=0;i<=nodes;i++){
                for(int j=0;j<=nodes;j++)
                    royfloyd_cost[i][j]=INF;
            }
        }
        for(int i=0;i<=nodes;i++)
            royfloyd_cost[i][i]=0;
        for(auto u:edge_set){
            royfloyd_cost[u.u][u.v]=u.w;
        }
        for (int k = 1; k <= nodes; k++) {
            for (int i = 1; i <= nodes; i++) {
                for (int j = 1; j <= nodes; j++) {
                    royfloyd_cost[i][j] = (royfloyd_cost[i][j] > royfloyd_cost[i][k] + royfloyd_cost[k][j] ?
                                           royfloyd_cost[i][k] + royfloyd_cost[k][j] : royfloyd_cost[i][j]);
                }
            }
        }
    }
    int royfloyd_distance(int u,int v){
        return royfloyd_cost[u][v];
    }

    ///topological sorting
    bool isDag(){
        vector <int> copy;
        topo.clear();
        copy.assign(in_deg.begin(),in_deg.end());
        queue <int>q;
        for(int i=1;i<=nodes;i++){
            if(copy[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int nod=q.front();
            q.pop();
            topo.push_back(nod);
            for(auto u:adjacency_list[nod]){
                copy[u.v]--;
                if(copy[u.v]==0){
                    q.push(u.v);
                }
            }
        }
        return (topo.size()==nodes);
    }
    vector <int> topological_sort(){
        if(topo.size()==0)
        isDag();
        return topo;
    }

    ///finding articulation nodes
    void dfs_art(int nod){
        dfs_order[nod]=++contor_art;
        for(auto u:adjacency_list[nod]){
            if(dfs_order[u.v]==-1){
                tata_art[u.v]=nod;
                copii_art[nod].push_back(u.v);
                dfs_art(u.v);
            }
        }
    }
    void calc_low(int nod){
        low[nod]=nod;
        for(auto u:adjacency_list[nod]){
            if(u.v!=tata_art[nod] and dfs_order[nod]>dfs_order[u.v]){
                low[nod]=(low[nod]>u.v?u.v:low[nod]);
            }
            if(dfs_order[nod]<dfs_order[u.v]){
                calc_low(u.v);
                low[nod]=(low[nod]>low[u.v]?low[u.v]:low[nod]);
            }
        }
    }
    vector <int> find_cut_vertex(){
        if(dfs_order.size()==0){
            vector <int> v;
            for(int i=0;i<=nodes;i++){
                dfs_order.push_back(-1);
                tata_art.push_back(-1);
                low.push_back(-1);
                copii_art.push_back(v);
            }
        }
        else{
            fill(dfs_order.begin(),dfs_order.end(),-1);
            fill(tata_art.begin(),tata_art.end(),-1);
            fill(low.begin(),low.end(),-1);
            for(int i=0;i<=nodes;i++) {
                copii_art[i].clear();
            }
        }
        contor_art=0;
        for(int i=1;i<=nodes;i++){
            if(dfs_order[i]==-1){
                dfs_art(i);
            }
        }
        for(int i=1;i<=nodes;i++){
            if(low[i]==-1){
                calc_low(i);
            }
        }
        int contor=0;
        vector <int> sol;
        if(copii_art[1].size()>=2){
            sol.push_back(1);
        }
        for(int i=2;i<=nodes;i++){
            for(auto u:copii_art[i]){
                if(dfs_order[i]<=low[u]) {
                    sol.push_back(i);
                }
            }
        }
        return sol;
    }
};
void dfs_prost(Graph g,int nod,int ok){
    //cout<<contor<<" "<<nod<<"\n";
    if(ok==false) {
        sol[contor].push_back(nod);
        if (is_artic[nod]) {
            return;
        }
    }
    for(auto u:g.copii_art[nod]){
        if(u==g.tata_art[nod]){
            continue;
        }
        if(ok==true){
            contor++;
            sol[contor].push_back(nod);
        }
        dfs_prost(g,u,false);
    }
}
int main(){
    int n,m,s;
    cin>>n>>m;
    Graph g(n);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        g.add_UEdge(a,b);
    }
    auto u=g.find_cut_vertex();
    for(int i=1;i<=n;i++){
        is_artic[i]=0;
    }
    for(auto uu:u){
        //cout<<uu<<" ";
        is_artic[uu]=true;
    }
    //cout<<"\n\n";
    for(auto uu:u){
        dfs_prost(g,uu,true);
    }
    cout<<contor<<"\n";
    for(int i=1;i<=contor;i++){
        for(auto uu:sol[i]){
            cout<<uu<<" ";
        }
        cout<<"\n";
    }
}

/*
10 8
1 4
1 5
2 3
4 5
6 7
7 8
6 8
9 10
*/