考虑到一个集合内的存在与否的特点，想到并查集。 拒绝装车->与已装的化合物形成易燃物。 简单并查集的应用。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define rez(i,x,y) for(int i=x;i>=y;i--) #define res(i,x,y) for(int i=x;i<=y;i++) #define INF 2100000000 #define ll long long #define clr(x) memset(x,0,sizeof(x)) using namespace std; const int maxn = 100000+50; int f[maxn],a,b,tot=0; int findset(int x){ return f[x]!=x?f[x]=findset(f[x]):x; } int main(){ for(int i=1;i<=maxn;i++)f[i]=i; while(scanf("%d",&a)!=EOF){ if(a==-1){ cout<<tot<<endl; tot=0; for(int i=1;i<=maxn;i++)f[i]=i; }else{ scanf("%d",&b); a=findset(a),b=findset(b); if(a==b)++tot; else f[a]=b; } } return 0; }大水题回顾系列。
