USACO 1206 Redistribution Gifts
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=501;
int best[MAXN];
vector< vector<int> > net(MAXN),netr(MAXN);
int n;
void goDFS(int start, set<int>& rset, vector< vector<int> >& lnet){
vector<bool> vis(n+1);
stack<int> s;
s.push(start);
int a;
while(!s.empty()){
a=s.top();
rset.insert(a);
s.pop();
for(int b :lnet[a]){
if(!vis[b]){
s.push(b);
vis[b]=true;
}
}
}
}
void goall(){
set<int> whole,ndfs,ndfsr,r1,r2;
for(int i=1;i<=n;i++){
whole.insert(i);
}
while(!whole.empty()){
int a=*whole.begin();
goDFS(a,ndfs,net);
goDFS(a,ndfsr,netr);
set_intersection(ndfs.begin(),ndfs.end(),ndfsr.begin(),ndfsr.end(),inserter(r1,r1.begin()));
for(auto vex:r1){
for(auto adj:net[vex]){
if(r1.count(adj)>0){
best[vex]=adj;
break;
}
}
}
set_difference(whole.begin(),whole.end(),r1.begin(),r1.end(),inserter(r2,r2.begin()));
whole=r2;
ndfs.clear();
ndfsr.clear();
r1.clear();
r2.clear();
}
}
int main()
{
//ifstream inf("redistributinggifs.in");
//ofstream outf("redistributinggifs.out");
//inf>>n;
cin>>n;
for(int i=1;i<=n;i++){
bool nodo=false;
for(int j=1;j<=n;j++){
int t;
//inf>>t;
cin>>t;
if(t==i){
nodo=true;;
}
if(!nodo){
net[i].push_back(t);
netr[t].push_back(i);
}
}
}
goall();
for(int i=1;i<=n;i++){
if(best[i]>0){
cout<<best[i]<<endl;
}else{
cout<<i<<endl;
}
}
//inf.close();
return 0;
}
