Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- using namespace std;
- using ll = long long;
- using ld = long double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- struct edge{
- int fr, to, id;
- };
- int n,m;
- vector <vector <edge> > G;
- const int bl = 2, gr = 1, wh = 0, inf = 2e9;
- vector <int> clr;
- void she(edge x){
- cout<<x.fr+1<<' '<<x.to+1<<' '<<x.id<<"\n";
- }
- void shG(){
- for (int i=0;i<n;++i){
- cout<<"i = "<<i<<"\n";
- for (int j = 0; j <G[i].size();++j){she(G[i][j]);}
- cout<<"\n\n";
- }
- }
- int curT = 0;
- set <int> pnt;//точки сочлен
- vector <int> tIn, tUp;
- void dfs(int v, int parId){//parId - id ребра по которомц пришли в v
- clr[v] = gr;
- tIn[v] = curT++;
- int kol = 0;
- if (parId == -1) kol--;
- for (auto e: G[v]){
- if (e.id == parId) continue;
- else if (clr[e.to] == wh){
- dfs(e.to, e.id);
- tUp[v] = min(tUp[v], tUp[e.to]);
- if (tIn[v] <= tUp[e.to]){
- kol++;
- }
- if (kol > 0){
- pnt.insert(e.fr);
- }
- }
- else if (clr[e.to] == gr){
- tUp[v] = min(tUp[v], tIn[e.to]);
- }
- }
- clr[v] = bl;
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n>>m;
- G.resize(n);
- clr.assign(n, wh);
- tIn.assign(n, inf);
- tUp.assign(n, inf);
- int id = 0;
- for (int i=0;i<m;++i){
- int a,b;
- cin>>a>>b;
- if (a>b) swap(a,b);
- a--; b--;
- edge any;
- any = {a, b, id};
- G[a].push_back(any);
- any = {b, a, id};
- G[b].push_back(any);
- id++;
- }
- //shG();
- for (int i = 0; i < n;++i){
- if (clr[i] == wh){
- dfs(i, -1);
- }
- }
- cout<<pnt.size()<<"\n";
- //sort(pnt.begin(), pnt.end());
- for (int i: pnt) cout<<i+1<<"\n";
- }
- /*
- 13 17
- 1 2
- 2 3
- 4 5
- 2 6
- 2 7
- 8 9
- 1 3
- 1 4
- 1 5
- 6 7
- 3 8
- 3 9
- 10 11
- 11 12
- 11 12
- 10 13
- 10 1
- 7
- 1
- 1
- 2
- 3
- 10
- 10
- 11
- */
- /*
- 13 17
- 1 2
- 2 3
- 4 5
- 2 6
- 2 7
- 8 9
- 1 3
- 1 4
- 1 5
- 6 7
- 3 8
- 3 9
- 10 11
- 11 12
- 11 12
- 10 13
- 10 1
- 10 13
- 1 2
- 2 3
- 4 5
- 2 6
- 2 7
- 8 9
- 1 3
- 1 4
- 1 5
- 6 7
- 3 8
- 3 9
- 9 10
- 9 12
- 1 2
- 2 3
- 4 5
- 2 6
- 2 7
- 8 9
- 1 3
- 1 4
- 1 5
- 6 7
- 3 8
- 3 9
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement