#564941 (C++14) No.1254 補強への架け橋

• 問題: No.1254 補強への架け橋
• ユーザー: startcpp
• 提出日時: 2020-10-09 22:45:39
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 847 bytes
• コンパイル時間: 682 ms
• コンパイル使用メモリ: 77,556 KB
• 実行使用メモリ: 10,288 KB
• 最終ジャッジ日時: 2023-09-27 18:42:40
• 合計ジャッジ時間: 11,513 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 5,744 KB
testcase_01	AC	3 ms; 5,736 KB
testcase_02	AC	3 ms; 5,708 KB
testcase_03	AC	4 ms; 5,784 KB
testcase_04	AC	3 ms; 5,616 KB
testcase_05	AC	3 ms; 5,620 KB
testcase_06	AC	3 ms; 5,700 KB
testcase_07	AC	3 ms; 5,644 KB
testcase_08	AC	3 ms; 5,692 KB
testcase_09	AC	4 ms; 5,636 KB
testcase_10	AC	4 ms; 5,848 KB
testcase_11	AC	3 ms; 5,616 KB
testcase_12	AC	3 ms; 5,688 KB
testcase_13	AC	3 ms; 5,684 KB
testcase_14	AC	4 ms; 5,704 KB
testcase_15	AC	3 ms; 5,704 KB
testcase_16	AC	3 ms; 5,688 KB
testcase_17	AC	3 ms; 5,644 KB
testcase_18	AC	3 ms; 5,932 KB
testcase_19	AC	3 ms; 5,900 KB
testcase_20	AC	3 ms; 5,732 KB
testcase_21	AC	3 ms; 5,628 KB
testcase_22	AC	3 ms; 5,936 KB
testcase_23	AC	3 ms; 5,848 KB
testcase_24	AC	3 ms; 5,780 KB
testcase_25	AC	3 ms; 5,680 KB
testcase_26	AC	3 ms; 5,844 KB
testcase_27	AC	3 ms; 5,628 KB
testcase_28	AC	4 ms; 5,640 KB
testcase_29	AC	3 ms; 5,808 KB
testcase_30	AC	3 ms; 5,692 KB
testcase_31	AC	4 ms; 5,872 KB
testcase_32	AC	4 ms; 5,848 KB
testcase_33	AC	4 ms; 5,644 KB
testcase_34	AC	3 ms; 5,688 KB
testcase_35	AC	3 ms; 5,684 KB
testcase_36	AC	3 ms; 5,680 KB
testcase_37	AC	4 ms; 5,692 KB
testcase_38	AC	3 ms; 5,996 KB
testcase_39	AC	3 ms; 5,676 KB
testcase_40	AC	3 ms; 5,752 KB
testcase_41	AC	4 ms; 5,640 KB
testcase_42	AC	3 ms; 5,892 KB
testcase_43	AC	4 ms; 5,820 KB
testcase_44	AC	3 ms; 5,708 KB
testcase_45	AC	4 ms; 5,716 KB
testcase_46	AC	4 ms; 5,712 KB
testcase_47	AC	4 ms; 5,756 KB
testcase_48	AC	4 ms; 5,712 KB
testcase_49	AC	4 ms; 5,688 KB
testcase_50	AC	4 ms; 5,720 KB
testcase_51	AC	4 ms; 5,776 KB
testcase_52	AC	4 ms; 5,684 KB
testcase_53	AC	4 ms; 5,712 KB
testcase_54	AC	4 ms; 5,664 KB
testcase_55	AC	4 ms; 5,672 KB
testcase_56	AC	4 ms; 5,692 KB
testcase_57	AC	4 ms; 5,772 KB
testcase_58	AC	4 ms; 5,776 KB
testcase_59	AC	3 ms; 5,776 KB
testcase_60	AC	3 ms; 5,756 KB
testcase_61	AC	4 ms; 5,712 KB
testcase_62	AC	3 ms; 5,684 KB
testcase_63	AC	10 ms; 6,088 KB
testcase_64	AC	5 ms; 5,996 KB
testcase_65	AC	8 ms; 5,920 KB
testcase_66	AC	7 ms; 6,160 KB
testcase_67	AC	5 ms; 5,892 KB
testcase_68	AC	7 ms; 6,000 KB
testcase_69	AC	8 ms; 6,016 KB
testcase_70	AC	5 ms; 5,820 KB
testcase_71	AC	5 ms; 5,952 KB
testcase_72	AC	8 ms; 6,012 KB
testcase_73	AC	5 ms; 5,820 KB
testcase_74	AC	8 ms; 6,260 KB
testcase_75	AC	7 ms; 5,876 KB
testcase_76	AC	4 ms; 5,736 KB
testcase_77	AC	7 ms; 5,828 KB
testcase_78	AC	9 ms; 6,276 KB
testcase_79	AC	9 ms; 6,048 KB
testcase_80	AC	9 ms; 6,308 KB
testcase_81	AC	10 ms; 6,100 KB
testcase_82	AC	9 ms; 6,232 KB
testcase_83	AC	91 ms; 9,996 KB
testcase_84	AC	78 ms; 10,140 KB
testcase_85	AC	48 ms; 8,320 KB
testcase_86	AC	68 ms; 9,288 KB
testcase_87	AC	76 ms; 9,780 KB
testcase_88	AC	13 ms; 6,344 KB
testcase_89	AC	81 ms; 9,908 KB
testcase_90	AC	50 ms; 8,396 KB
testcase_91	AC	40 ms; 8,204 KB
testcase_92	AC	22 ms; 6,928 KB
testcase_93	AC	65 ms; 9,140 KB
testcase_94	AC	60 ms; 8,824 KB
testcase_95	AC	58 ms; 8,756 KB
testcase_96	AC	82 ms; 9,704 KB
testcase_97	AC	34 ms; 7,748 KB
testcase_98	AC	80 ms; 9,796 KB
testcase_99	AC	47 ms; 8,428 KB
testcase_100	AC	84 ms; 10,024 KB
testcase_101	AC	20 ms; 6,732 KB
testcase_102	AC	11 ms; 6,192 KB
testcase_103	AC	21 ms; 6,844 KB
testcase_104	AC	29 ms; 7,276 KB
testcase_105	AC	66 ms; 9,228 KB
testcase_106	AC	37 ms; 7,748 KB
testcase_107	AC	82 ms; 9,984 KB
testcase_108	AC	81 ms; 9,972 KB
testcase_109	AC	64 ms; 9,044 KB
testcase_110	AC	57 ms; 9,036 KB
testcase_111	AC	61 ms; 8,936 KB
testcase_112	AC	28 ms; 7,136 KB
testcase_113	AC	56 ms; 8,800 KB
testcase_114	AC	37 ms; 7,700 KB
testcase_115	AC	14 ms; 6,408 KB
testcase_116	AC	41 ms; 7,976 KB
testcase_117	AC	28 ms; 7,380 KB
testcase_118	AC	76 ms; 9,664 KB
testcase_119	AC	46 ms; 8,300 KB
testcase_120	AC	74 ms; 9,696 KB
testcase_121	AC	24 ms; 7,080 KB
testcase_122	AC	41 ms; 8,128 KB
testcase_123	AC	3 ms; 5,628 KB
testcase_124	AC	98 ms; 10,288 KB
testcase_125	AC	96 ms; 10,212 KB

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
vector<int> et[100000];
int a[100000], b[100000];
int inV[100000];

int main() {
	int i;
	
	cin >> n;
	rep(i, n) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		et[a[i]].push_back(b[i]);
		et[b[i]].push_back(a[i]);
		inV[a[i]]++;
		inV[b[i]]++;
	}
	
	queue<int> que;
	rep(i, n) {
		if (inV[i] == 1) {
			que.push(i);
		}
	}
	
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int nv : et[v]) {
			inV[nv]--;
			if (inV[nv] == 1) {
				que.push(nv);
			}
		}
	}
	
	vector<int> ans;
	rep(i, n) {
		if (inV[a[i]] >= 2 && inV[b[i]] >= 2) {
			ans.push_back(i);
		}
	}
	
	cout << ans.size() << endl;
	rep(i, ans.size()) {
		cout << ans[i] + 1;
		if (i + 1 < ans.size()) cout << " ";
	}
	cout << endl;
	
	return 0;
}