Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.1 kB
4
Indexable
Never
//
// Created by jin ho Jeon on 2023/10/23.
//

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

vector<vector<pair<int,int> > > sccs;
stack<pair<int,int> > edges;
vector<int> G[10001];
bool vis[10001];
int low[10001];
int pre[10001];
set<int > vertexes;

int cnt = 0;

int v;
int e;

int bcc(int cur, int prev = -1){

    pre[cur] = low[cur] = ++cnt;
    vis[cur] = true;
    int children = 0;


    for(int nxt : G[cur]){
        if( nxt == prev) continue;

        if(vis[nxt]){
            low[cur] = min(low[cur], pre[nxt]);
            pair<int, int> cur_edge = make_pair(cur,nxt);
            edges.push(cur_edge);
        }else{ // not visited
            pair<int,int> cur_edge = make_pair(cur,nxt);

            edges.push(cur_edge);
            bcc(nxt, cur);
            low[cur] = min(low[nxt], low[cur]);
            if(low[nxt]>=pre[cur]){
                vector<pair<int,int> > cur_bcc;
                while (!edges.empty()){
                    pair<int, int> edge = edges.top();
                    edges.pop();
                    cur_bcc.push_back(edge);
                    if(edge.first == cur && edge.second == nxt) break;
                }

                if(!cur_bcc.empty())
                    sccs.push_back(cur_bcc);
            }
            ++children;
        }
    }

    if(children > 1 && prev == -1){

    }
    // output

    //
    return 0;
}

int main(){
    cin >> v >> e;
    int start, end;

    for (int i = 0; i < e; ++i) {
        cin >> start >> end;
        G[start].push_back(end);
        G[end].push_back(start);
    }
    for(int i = 1;i<=8;i++){
        sort(G[i].begin(), G[i].end());
    }
    bcc(6,0);

    int bcc_count = sccs.size();
    for (int i = 0; i < bcc_count; ++i) {
        cout << i+1 << "th \n";
        for (int j = 0; j < sccs[i].size(); j++){
            cout << sccs[i][j].first << " " << sccs[i][j].second << "\n";
        }
        cout << '\n';
    }
    return bcc_count;


    return 0;
}