<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12

      割邊模板

      // 無向雙連通例子.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。
      //
      
      /*
      http://oj.daimayuan.top/course/23/problem/983
      
      給一個n個點m條邊的無向連通圖,從小到大輸出所有割邊的編號。注意:邊從1開始標號。
      
      輸入格式
      第一行包含兩個數n,m(1≤n≤105,1≤m≤2×105)。
      
      接下來m行,每行兩個整數u,v表示一條無向邊,沒有自環,但可能有重邊。
      
      輸出格式
      首先輸出一個整數,表示割邊個數。接下來一行,若干個從小到大的數,表示割邊的編號。
      
      樣例輸入
      7 8
      1 2
      2 3
      3 4
      2 5
      4 5
      5 6
      5 7
      5 7
      樣例輸出
      2
      1 6
      */
      
      #include <iostream>
      #include <vector>
      #include <cstring>
      
      
      using namespace std;
      
      int n, m;
      
      const int N = 100010, M = 400010;
      int h[N], e[M], ne[M], idx;
      int dfn[N], low[N], timestamp;
      int stk[N], top;
      int id[N], dcc_cnt;
      bool bridge[M];
      
      void add(int a, int b) {
      	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
      }
      
      void tarjan(int u,int from) {
      	dfn[u] = low[u] = ++timestamp;
      	stk[++top] = u;
      
      	for (int i = h[u]; i != -1; i = ne[i]) {
      		int j = e[i];
      		if (!dfn[j]) {
      			tarjan(j, i);
      			low[u] = min(low[u], low[j]);
      			if (dfn[u] < low[j]) {
      				bridge[i] = bridge[i ^ 1] = true;
      			}
      		}
      		else if (i != (from ^ 1))
      			low[u] = min(low[u], dfn[j]);
      	}
      
      	if (dfn[u] == low[u]) {
      		++dcc_cnt;
      		int y;
      		do {
      			y = stk[top--];
      			id[y] = dcc_cnt;
      		} while (y != u);
      	}
      
      }
      
      
      int main()
      {
      	cin >> n >> m;
      	memset(h, -1, sizeof h);
      	for(int i= 0;i < m;i++){
      		int a, b;
      		cin >> a >> b;
      		add(a, b); add(b, a);
      	}
      
      	//tarjan(1,-1);
      
          for (int i = 1; i <= n; i++) {
      		if (!dfn[i]) tarjan(i, -1);
      	}
      
      	vector<int> ans;
      	for (int i = 1; i <= m; i++) {
      		if (bridge[(i-1)* 2]) {
      			ans.push_back(i);
      		}
      	}
      	cout << ans.size() << endl;
      	for (int i = 0; i < ans.size(); i++) {
      		cout << ans[i] << " ";
      	}
      
      	return 0;
      }
      
      // 無向雙連通例子.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。
      //
      
      /*
      http://oj.daimayuan.top/course/23/problem/983
      
      給一個n個點m條邊的無向連通圖,從小到大輸出所有割邊的編號。注意:邊從1開始標號。
      
      輸入格式
      第一行包含兩個數n,m(1≤n≤105,1≤m≤2×105)。
      
      接下來m行,每行兩個整數u,v表示一條無向邊,沒有自環,但可能有重邊。
      
      輸出格式
      首先輸出一個整數,表示割邊個數。接下來一行,若干個從小到大的數,表示割邊的編號。
      
      樣例輸入
      7 8
      1 2
      2 3
      3 4
      2 5
      4 5
      5 6
      5 7
      5 7
      樣例輸出
      2
      1 6
      */
      
      #include <iostream>
      #include <vector>
      
      
      
      using namespace std;
      
      const int SIZE = 200010;
      int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
      int dfn[SIZE], low[SIZE], n, m, tot, num;
      bool bridge[SIZE * 2];
      void add(int x, int y) {
      	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
      }
      
      void tarjan(int x, int in_edge) {
      	dfn[x] = low[x] = ++num;
      	for (int i = head[x]; i; i = Next[i]) {
      		int y = ver[i];
      		if (!dfn[y]) {
      			tarjan(y, i);
      			low[x] = min(low[x], low[y]);
      			if (low[y] > dfn[x]) {
      				bridge[i] = bridge[i ^ 1] = true;
      			}
      		}
      		else if(i != (in_edge^1)) {
      			low[x]=min(low[x],dfn[y]);
      		}
      	}
      }
       
      
      
      
      int main()
      {
      	cin >> n >> m;
      	tot = 1;
      	for (int i = 1; i <= m; i++) {
      		int x, y;
      		cin >> x >> y;
      		add(x, y); add(y, x);
      	}
      	for (int i = 1; i <= n; i++) {
      		if (!dfn[i]) tarjan(i, 0);
      	}
      	vector<int> ans;
      	for (int i = 2; i < tot; i += 2) {
      		if (bridge[i]) {
      			ans.push_back(i / 2);
      		}
      	}
      	cout << ans.size() << endl;
      	for (int i = 0; i < ans.size(); i++) {
      		cout << ans[i] << " ";
      	}
      
      
      	return 0;
      }
      

      posted on 2025-08-10 13:54  itdef  閱讀(14)  評論(0)    收藏  舉報

      導航

      主站蜘蛛池模板: 国产AV影片麻豆精品传媒| 国产美女被遭强高潮免费一视频 | 深夜福利啪啪片| 极品少妇的粉嫩小泬看片 | 激情综合网激情五月俺也想| 欧产日产国产精品精品| 亚洲国产日韩一区三区| 55大东北熟女啪啪嗷嗷叫| 思南县| 久久久久久九九99精品| 久久亚洲精品成人av无| 护士的小嫩嫩好紧好爽| 国产目拍亚洲精品二区| 偷拍美女厕所尿尿嘘嘘小便| 国产精品天天狠天天看| 新野县| 国产福利永久在线视频无毒不卡| 亚洲性夜夜天天天| 日韩中文字幕有码av| 狠狠色噜噜狠狠狠狠2021| 大陆精大陆国产国语精品| 日韩精品区一区二区三vr| 亚洲成av人片天堂网| 久久亚洲精品中文字幕无| 国产成人精品无码片区在线观看 | 亚洲av无码精品色午夜蛋壳| 国产综合色一区二区三区| 亚洲日本韩国欧美云霸高清| 国产日韩精品一区在线不卡| 999精品色在线播放| 国产精品视频亚洲二区| 夜鲁夜鲁很鲁在线视频 视频| 国产盗摄xxxx视频xxxx| 网友自拍视频一区二区三区 | 施甸县| 日韩精品成人区中文字幕| 国产精品午夜福利导航导| 亚洲国产成人av毛片大全| 日本激情久久精品人妻热| 亚洲熟妇自偷自拍另类| 欧美精品日韩精品一卡|