scc36 @ 2024-02-04 10:04:25
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,fl,s,b[1000001],a[1000001];
int fx,fy,e[1000001],f[1000001],ff[1000001],t,ss;
struct no{
int x,y;
}x[1000001];
int fi(int t){
if(f[t]==t) return t;
else return f[t]=fi(f[t]);
}
bool cmp(no t,no w){ //排序
if(b[t.x]<b[w.x]&&b[t.y]<b[w.y]) return 0;
else if(b[t.x]>b[w.x]&&b[t.y]<b[w.y]) return 0;
else if(b[t.x]<b[w.x]&&b[t.y]>b[w.y]) return 0;
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=m;i++) cin>>x[i].x>>x[i].y;
for(i=1;i<=n;i++) cin>>a[i],b[a[i]]=i;
sort(x+1,x+m+1,cmp);
t=1;
for(i=n;i>=1;i--){
e[a[i]]=1;ss++; //连通块++
while(e[x[t].x]==1&&e[x[t].y]==1&&t<=m){
fx=fi(x[t].x),fy=fi(x[t].y);
if(fx!=fy) ss--,f[fx]=fy; //连通块--
t++;
}
if(ss==1) b[i]=1;
else b[i]=0;
}
for(i=1;i<=n;i++)
if(b[i]) cout<<"YES\n";
else cout<<"NO\n";
}个人认为思想正确，但只有十分/(ㄒoㄒ)/~~
那位大佬来看看？
by Gambler_Super @ 2024-02-04 10:16:26
@scc36 不会
by ChampionCyan @ 2024-02-17 11:01:10
我这跟你一样，10pts
555……
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 1;
vector<int> e[MAXN], q;
int fa[MAXN], op[MAXN];
bool isopen[MAXN] = {};
stack<bool> ans;
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
e[a].push_back(b), e[b].push_back(a);
}
for (int i = 1; i <= n; i++)
fa[i] = i;
printf("YES\n");
for (int i = n - 1; i > 1; i--)
scanf("%d", &op[i]);
for (int i = 2; i < n; i++) {
int open = op[i];
isopen[open] = true, q.push_back(open);
for (int edge : e[i]) {
int fe = find(edge);
for (int j = 1; j <= n; j++)
if (find(j) == fe && j != edge)
fa[j] = open;
fa[edge] = open;
}
int father = q[0];
bool ok = true;
for (int j = 1; j < (int)q.size(); j++)
if (find(j) != father) {
ok = false;
break;
}
ans.push(ok);
}
while (!ans.empty()) {
if (ans.top())
printf("YES\n");
else
printf("NO\n");
ans.pop();
}
printf("YES\n");
return 0;
}by junwei @ 2024-05-15 20:49:54
@weah964 你的错误和我的是一样的 scc36的代码我没看出啥
@weah964 把fe删掉 每次在循环里使用find函数 因为每次访问时,并查集一直在变化 fe的值并不是最新并查集的询问而是改变前并查集的询问
by ChampionCyan @ 2024-05-16 18:00:02
@junweili
具体点吧，代码咋改？蒟蒻真看不懂什么意思
by ChampionCyan @ 2024-05-16 18:07:35
@junweili
笑死-ing
by junwei @ 2024-05-16 22:28:23
@weah964 会改的吧 加油
by junwei @ 2024-05-16 22:36:47
nb我改了一下你的代码 其它都TLE了... 幸好你自己已经AC了
by ChampionCyan @ 2024-05-17 17:16:20
@junweili
我这个TLE正常，时间复杂度
for (int i = 2; i < n; i++) {
int open = op[i];
isopen[open] = true, q.push_back(open);
for (int edge : e[i]) {
int fe = find(edge);
for (int j = 1; j <= n; j++)
if (find(j) == fe && j != edge)
fa[j] = open;
fa[edge] = open;
}
int father = q[0];
bool ok = true;
for (int j = 1; j < (int)q.size(); j++)
if (find(j) != father) {
ok = false;
break;
}
ans.push(ok);
}你看，两层循环，就是复杂度都超标了
by junwei @ 2024-05-17 20:26:49
// Problem: P6121 [USACO16OPEN] Closing the Farm G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6121
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int h[N], e[N], ne[N], idx;
bool st[N];
int p[N], q[N];
int res[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h);
int a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++)
{
cin >> q[i];
st[q[i]] = true;
}
int cnt = 0;
for (int i = n; i; i--)
{
cnt++;
for (int j = h[q[i]]; ~j; j = ne[j])
{
int k = e[j];
a = find(q[i]), b = find(k);
if (a != b && !st[k])
{
p[a] = b;
cnt--;
}
}
st[q[i]] = false;
res[i] = cnt;
}
for (int i = 1; i <= n; i++)
if (res[i] == 1) cout << "YES\n";
else cout << "NO\n";
return 0;
}by junwei @ 2024-05-17 20:29:42
@weah964 你可以看一下 add函数是链式前项星