1068번 - 트리
다른 유저의 질문에 적혀있는 케이스와 문제 예제케이스에 대해서모두 올바르게 나왔는데 돌려보니 틀렸다고 하네요
p.s. 밑에 코드가 잘리네요...
#include <iostream>#include <queue>using namespace std;
int d[53][53]={0,},visit[53]={0,},n,cut,cnt=0;queue<int> rootidx;void leaf(int root){ visit[root]=1; int t=0;for(int i=0;i<n;i++){if(visit[i]==0&&d[root][i]){ t++; leaf(i); }} if(t==0){ cnt++;}}int main(){ cin>>n; for(int i=0;i<n;i++){ int a; cin>>a; if(a==-1){ rootidx.push(i); } else{ d[i][a]=d[a][i]=1; }} cin>>cut; for(int i=0;i<n;i++){ d[cut][i]=d[i][cut]=0;} while(rootidx.size()){ leaf(rootidx.front()); rootidx.pop();} cout<<cnt<<endl; return 0;}
3
-1 0 0
0
해보시면 답이 0이 나와야 되는데 1이 나오네요
apink 님 감사합니다^^
등잔 밑에 있는 당연한 케이스를 생각치 못했네요..
댓글을 작성하려면 로그인해야 합니다.
imscs22 6년 전
다른 유저의 질문에 적혀있는 케이스와 문제 예제케이스에 대해서모두 올바르게 나왔는데 돌려보니 틀렸다고 하네요
p.s. 밑에 코드가 잘리네요...
#include <iostream>
#include <queue>
using namespace std;
int d[53][53]={0,},visit[53]={0,},n,cut,cnt=0;
queue<int> rootidx;
void leaf(int root){
visit[root]=1;
int t=0;
for(int i=0;i<n;i++){
if(visit[i]==0&&d[root][i]){
t++;
leaf(i);
}
}
if(t==0){
cnt++;
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
int a;
cin>>a;
if(a==-1){
rootidx.push(i);
}
else{
d[i][a]=d[a][i]=1;
}
}
cin>>cut;
for(int i=0;i<n;i++){
d[cut][i]=d[i][cut]=0;
}
while(rootidx.size()){
leaf(rootidx.front());
rootidx.pop();
}
cout<<cnt<<endl;
return 0;
}