QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129087 | #996. 割点 | Terdy# | WA | 1ms | 8308kb | C++14 | 1.2kb | 2023-07-21 21:02:42 | 2023-07-21 21:02:43 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n , m;
int ecnt = 1 , head[N] , to[N] , nxt[N];
int ans , rt , DFN[N] , LOW[N] , Tcnt , cut[N];
void AddEdge(int u , int v) {nxt[++ecnt] = head[u] , head[u] = ecnt , to[ecnt] = v;}
void tarjan(int u , int fa)
{
int cnt = 0;
DFN[u] = LOW[u] = ++Tcnt;
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(!DFN[v])
{
cnt++;
tarjan(v , u);
LOW[u] = min(LOW[u] , LOW[v]);
if(u != rt && LOW[v] >= DFN[u]) cut[u] = 1;
}
LOW[u] = min(LOW[u] , LOW[v]);
}
// cout << u << ' ' << rt << ' ' << cnt << endl;
if(!fa && cnt > 1) cut[u] = 1;
}
void Tarjan()
{
for(int i = 1; i <= n; i++) if(!DFN[i])
rt = i , tarjan(i , 0);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 1 , u , v; i <= m; i++) cin >> u >> v , AddEdge(u , v) , AddEdge(v , u);
Tarjan();
for(int i = 1; i <= n; i++) if(cut[i]) ans++;
cout << ans << endl;
for(int i = 1; i <= n; i++) if(cut[i]) cout << i << endl;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 8308kb
input:
12783 21968 4933 7832 8238 2739 3628 7841 9169 6390 7850 8797 8120 8710 5306 9807 10166 2063 2666 5157 5015 4651 4790 12586 10366 7137 12440 7218 6330 3670 2735 8492 1968 2750 6237 1112 6578 9221 743 3820 7155 4583 2537 9747 11331 9916 4454 5631 2978 10340 5293 1803 4944 4296 11800 2742 7903 2018 10...
output:
420 29 33 91 144 151 155 166 187 192 219 223 239 250 256 265 315 338 347 388 414 459 538 574 653 728 752 858 871 872 930 938 959 964 988 1010 1015 1046 1068 1084 1124 1180 1186 1235 1293 1319 1395 1459 1511 1544 1558 1568 1577 1603 1646 1693 1880 1927 1948 1953 1955 1978 2018 2033 2097 2161 2184 219...
result:
wrong answer 1st numbers differ - expected: '1440', found: '420'