QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#746075 | #9525. Welcome to Join the Online Meeting! | ssx | WA | 2ms | 9952kb | C++20 | 2.8kb | 2024-11-14 13:17:07 | 2024-11-14 13:17:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 3e5 + 50;
vector<int> e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], cnt;
void tarjan(int x)
{
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y : e[x])
{
if (!dfn[y])
{//若y尚未访问
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instk[y])//若y已访问且在栈中
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{//若x是SCC的根
int y; ++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt; //y属于哪个SCC
} while (y != x);
}
}
ll st[N], vis[N];
ll in[N], out[N];
void bfs(ll s)
{
cout << s << '\n';
vector<ll> v;
queue<ll> q;
q.push(s);
vis[s] = 1;
while (!q.empty())
{
auto tx = q.front();
q.pop();
v.clear();
for (auto it : e[tx])
{
if (vis[it] == 1) continue;
vis[it] = 1;
v.push_back(it);
q.push(it);
}
if (v.size() == 0) continue;
cout << tx << ' ' << v.size() << ' ';
for (auto it : v) cout << it << ' ';
cout << '\n';
}
}
void solve()
{
ll n, m, k, a0, res = 0, start = 0;
cin >> n >> m >> k;
for (int i = 1; i <= k; i++)
{
cin >> a0;
st[a0] = 1;
}
ll u, v;
for (int i = 1; i <= m; i++)
{
cin >> u >> v;
if (st[u] == 1 && st[v] == 1) continue;
if (st[u] == 1 && st[v] == 0) e[v].push_back(u);
else
{
if (st[u] == 0 && st[v] == 1) e[u].push_back(v);
else
{
e[u].push_back(v);
e[v].push_back(u);
}
}
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int x = 1; x <= n; x++)
{
for (int y : e[x])
{
ll a = scc[x], b = scc[y];
if (a != b) in[scc[y]] ++;
}
} //缩点后建拓扑图
for (int i = 1; i <= cnt; i++)
{
if (in[i] == 0)
{
res ++;
start = i;
}
}
if (res > 1) cout << "NO";
else
{
cout << "YES" << '\n';
for (int i = 1; i <= n; i++)
{
if (scc[i] == start)
{
start = i;
break;
}
}
bfs(start);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll T = 1;
//cin >> T;
while (T --)
{
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9952kb
input:
4 5 2 3 4 1 2 1 3 2 3 3 4 2 4
output:
YES 1 1 2 2 3 2 1 4
result:
wrong answer Token parameter [name=pans] equals to "YES", doesn't correspond to pattern "Yes|No"