Untitled
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; }