結果
| 問題 | No.3508 OR Mapping |
| コンテスト | |
| ユーザー |
 nagasan0210
|
| 提出日時 | 2026-04-19 12:55:51 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 727 ms / 2,000 ms |
| コード長 | 6,297 bytes |
| 記録 | |
| コンパイル時間 | 3,288 ms |
| コンパイル使用メモリ | 359,368 KB |
| 実行使用メモリ | 134,912 KB |
| 最終ジャッジ日時 | 2026-04-19 12:56:25 |
| 合計ジャッジ時間 | 22,791 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 65 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(a); i > (int)(b); i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define PQ priority_queue<int, vector<int>, greater<int>>
#define PQ_g priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
const int d4[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int d8[8][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
void Yes(bool b) {cout << (b ? "Yes" : "No") << endl;}
int main() {
int n, m, k; cin >> n >> m >> k;
vector<vector<int>> graph(n + 1, vector<int>(0));
vector<vector<int>> inv_graph(n + 1, vector<int>(0));
rep(i, 1, m + 1) {
int u, v; cin >> u >> v;
graph[u].push_back(v);
inv_graph[v].push_back(u);
}
vector<vector<int>> SCC(0);
{
stack<int> st;
{
vector<bool> visited(n + 1);
auto dfs = [&](auto&& self, int pos) -> int {
if (visited[pos]) return 0;
visited[pos] = true;
for (auto &nex: graph[pos]) {
if (visited[nex]) continue;
self(self, nex);
}
st.push(pos);
return 0;
};
rep(i, 1, n + 1) {
if (visited[i]) continue;
dfs(dfs, i);
}
}
{
vector<bool> visited(n + 1);
auto dfs = [&](auto&& self, int pos, vector<int>* group) -> int {
if (visited[pos]) return 0;
visited[pos] = true;
for (auto &nex: inv_graph[pos]) {
if (visited[nex]) continue;
self(self, nex, group);
}
group -> push_back(pos);
return 0;
};
while (!st.empty()) {
int i = st.top();
st.pop();
if (visited[i]) continue;
vector<int> group0;
dfs(dfs, i, &group0);
SCC.push_back(group0);
}
}
}
vector<int> v_to_scc(n + 1, -1);
rep(i, 0, SCC.size()) {
for (auto &v: SCC[i]) {
v_to_scc[v] = i;
}
}
rep(i, 0, SCC.size()) {
for (auto &v: SCC[i]) {
v_to_scc[v] = i;
}
}
vector<vector<int>> compressed_graph(SCC.size(), vector<int> (0));
vector<bool> has_one_v(SCC.size());
bool flg1 = true;
//すべての強連結成分は、１頂点のものを除き二部グラフでない
{
const int INF = (1 << 30);
vector<int> dist(n + 1, INF);
vector<bool> visited(n + 1);
rep(i, 0, SCC.size()) {
if (SCC[i].size() == 1) {
has_one_v[i] = true;
continue;
}
//二部グラフか？
bool flg2 = true;
int start = SCC[i][0];
queue<int> Q;
dist[start] = 0;
Q.push(start);
while (!Q.empty()) {
int pos = Q.front();
Q.pop();
if (visited[pos]) continue;
visited[pos] = true;
for (auto &nex: graph[pos]) {
if (visited[nex] || v_to_scc[pos] != v_to_scc[nex]) continue;
dist[nex] = min(dist[nex], dist[pos] + 1);
Q.push(nex);
}
}
for (auto &u: SCC[i]) {
for (auto &v: graph[u]) {
if (v_to_scc[u] != v_to_scc[v]) continue;
if (dist[u] % 2 == dist[v] % 2) {
flg2 = false;
break;
}
}
if (!flg2) break;
}
if (flg2) {
flg1 = false;
break;
}
}
}
if (!flg1) {
cout << "No" << endl;
exit(0);
}
rep(u, 1, n + 1) {
for (auto &v: graph[u]) {
if (v_to_scc[u] != v_to_scc[v]) {
compressed_graph[v_to_scc[u]].push_back(v_to_scc[v]);
}
}
}
rep(i, 0, SCC.size()) {
set<int> s0;
for (auto &j: compressed_graph[i]) s0.insert(j);
compressed_graph[i].resize(0);
for (auto &j: s0) compressed_graph[i].push_back(j);
}
//トポロジカルソート
vector<int> tp_sorted(0);
{
vector<int> in_cnt(SCC.size());
rep(u, 0, SCC.size()) {
for (auto &v: compressed_graph[u]) {
in_cnt[v]++;
}
}
stack<int> st;
rep(u, 0, SCC.size()) {
if (in_cnt[u] == 0) st.push(u);
}
while (!st.empty()) {
int pos = st.top();
st.pop();
tp_sorted.push_back(pos);
for (auto &nex: compressed_graph[pos]) {
in_cnt[nex]--;
if (in_cnt[nex] == 0) st.push(nex);
}
}
}
rep(i, 0, SCC.size() - 1) {
//トポロジカルソートで隣接する部分はつながっているか？
bool flg2 = false;
int u = tp_sorted[i];
for (auto &v: compressed_graph[u]) {
if (v == tp_sorted[i + 1]) {
flg2 = true;
break;
}
}
if (!flg2) {
cout << "No" << endl;
exit(0);
}
}
//頂点1はトポロジカルソートの先頭に含まれるか？
if (tp_sorted[0] != v_to_scc[1]) {
cout << "No" << endl;
exit(0);
}
//先頭は1頂点でないか？
if (has_one_v[tp_sorted[0]]) {
cout << "No" << endl;
exit(0);
}
rep(i, 0, SCC.size() - 1) {
//トポロジカルソートで隣接する部分は、「ともに1頂点」ではないか？
if (has_one_v[tp_sorted[i]] && has_one_v[tp_sorted[i + 1]]) {
cout << "No" << endl;
exit(0);
}
}
cout << "Yes" << endl;
}