問題
http://community.topcoder.com/stat?c=problem_statement&pm=10275&rd=13697
有向グラフが存在し、各ノードに対しどのノードが親であるかの情報が与えられる。
ただし、根のノードはー１が入っている。
この有向グラフに、ある指定されたノードが削除され、その子となっているノードも削除される。
このとき、元のノードの葉であり削除されていない葉の数を求める。
解き方
元のグラフの葉のノードは、どのノードからも参照されていないノードになる。
また、あるノードが削除されたときに、その子であるノードはＢＦＳで探索できる。
上記の２つの処理を行うことで答えを求めることができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CellRemoval {
public: int cellsLeft(vector<int> parent, int deletedCell) {
int n=parent.size();
int p[n+1];
memset(p,1,sizeof(p));
FORE(i,0,n)p[parent[i]]=0;
queue<int> q;
q.push(deletedCell);
while(!q.empty()){
int x=q.front();
q.pop();
p[x]=0;
FORE(i,0,n)if(parent[i]==x)q.push(i);
}
int ret=0;
FORE(i,0,n)if(p[i])ret++;
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CellRemoval {
public: int cellsLeft(vector<int> parent, int deletedCell) {
int n=parent.size();
int p[n+1];
memset(p,1,sizeof(p));
FORE(i,0,n)p[parent[i]]=0;
queue<int> q;
q.push(deletedCell);
while(!q.empty()){
int x=q.front();
q.pop();
p[x]=0;
FORE(i,0,n)if(parent[i]==x)q.push(i);
}
int ret=0;
FORE(i,0,n)if(p[i])ret++;
return ret;
}
};