40分求助

P1330 封锁阳光大学

更正代码后是60分了,t++只取决于边不为0的时候 ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 1e6; int n,m; int ans = 0; struct edge{ vector<int> v; int point; }; edge a[N]; int f[N]; void init(){ for(int i = 1;i<=n;++i) f[i] = i; } int findfather(int x){ if(x==f[x]) return x; return f[x] = findfather(f[x]); } void merge(int a,int b){ int fa = findfather(a); int fb = findfather(b); if(fa!=fb){ f[fa] = fb; } } bool cmp(edge a,edge b){ return a.v.size()>b.v.size(); } int main(){ cin>>n>>m; init(); for(int i = 1;i<=m;++i){ int x,y; cin>>x>>y; a[x].point = x; a[x].v.push_back(y); a[y].point = y; a[y].v.push_back(x); } sort(a+1,a+n+1,cmp); int t = 0; for(int i = 1;i<=n;++i){ if(findfather(a[i].point) == a[i].point){ for(int j = 0;j<a[i].v.size();++j){ merge(a[i].v[j],a[i].point); } ans+=a[i].v.size(); //单个点完全独立,那么就不需要放出河蟹 if(a[i].v.size()!=0) t++; } } if(ans<m) cout<<"Impossible"; else cout<<t; return 0; } ```
by Rhss @ 2022-10-25 15:26:13


|