OLE求调
查看原帖
OLE求调
1530149
zzh_we_love_you楼主2025/7/27 19:14
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,k,dfn[2*N],low[2*N],num,cnt,belong[2*N],vis[2*N];
vector<int>e[2*N],a[N];
stack<int>st;
void dfs(int u){
	dfn[u]=low[u]=++num;
	st.push(u);
	vis[u]=1;
	for(int v:e[u]){
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}if(dfn[u]==low[u]){
		cnt++;
		while(1){
			int t=st.top();
			belong[t]=cnt;
			vis[t]=0;
			st.pop();
			if(t==u)break;
		}
	}
}
void solve(){
	for(int i=1;i<=n;i++){
		cin>>k;
		for(int j=1;j<=k;j++){
			int x;
			cin>>x;
			e[i].push_back(x+n);
		}
	}for(int i=1;i<=n;i++){
		int x;
		cin>>x;
        e[x+n].push_back(i);
	}for(int i=1;i<=2*n;i++){
		if(!dfn[i])dfs(i);
	}
	for(int j=n+1;j<=2*n;j++){
		for(int i=1;i<=n;i++){
			if(belong[i]==belong[j]){
				a[i].push_back(j-n);
			}
		}
	}for(int i=1;i<=n;i++){
		cout<<a[i].size()<<" ";
		for(int j:a[i])cout<<j<<" ";
		cout<<endl;
	}
}
void init(){
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(belong,0,sizeof belong);
    memset(vis,0,sizeof vis);
    while(!st.empty())st.pop();
	cnt=num=0;
	for(int i=1;i<=2*n;i++)e[i].clear();
	for(int i=1;i<=n;i++)a[i].clear();
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	while(cin>>n&&n!=EOF){
		init();
		solve();
	}
}
2025/7/27 19:14
加载中...