题解:
可能有人在多个圈子,那么这几个圈子合并为一个部落,一个做法就是将圈子转化为有向图,最后求出的缩点就是部落个数。再查询是否在一个缩点当中。
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 1e18
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin()+1,a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define safe_map unordered_map<int, int, custom_hash>
using namespace std;
typedef pair<int,int>pii;
const int N =1e4+7;
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
vct<int>e[N];
int low[N],dfn[N],tot,cnt;
int scc[N];
bool vis[N];
stack<int>stk;
void tarjan(int x){
low[x]=dfn[x]=++tot;
stk.push(x);
vis[x]=1;
for(auto t: e[x]){
if(!dfn[t]){
tarjan(t);
mmin(low[x],low[t]);
}
else if(vis[t]){
mmin(low[x],dfn[t]);
}
}
if(low[x]==dfn[x]){
int y;cnt++;
do{
y=stk.top();stk.pop();
vis[y]=0;
scc[y]=cnt;
}while(y!=x);
}
}
signed main()
{IOS
int X;cin>>X;
set<int>all;
while(X--){
int n;cin>>n;
vct<int>a(n+1);
for(int i=0;i<n;i++){
cin>>a[i];
all.insert(a[i]);
}
a[n]=a[0];
for(int i=0;i<n;i++){
e[a[i]].pb(a[i+1]);
}
}
int n=all.size();
cout<<n<<" ";
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
cout<<cnt<<endl;
int q;cin>>q;
while(q--){
int x,y;cin>>x>>y;
if(scc[x]==scc[y])cout<<"Y\n";
else cout<<"N\n";
}
return 0;
}