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;
}