Code: Select all
input:
5
0
0
output:
5
The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.
lets forget it. u have to solve it considering a specific approch. 
Code: Select all
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
int d[101][101],num[101],p[101],l[101],ti,r[101];
void vis(int u,int f,int n){
int num1=0,num2=0;
p[u]=f;
num[u]=ti++;
l[u]=num[u];
for(int i=1;i<=n;i++)
if(d[u][i])
if(i!=f){
if(num[i]==-1){
vis(i,u,n);
l[u]=min(l[u],l[i]);
}
else
l[u]=min(l[u],num[i]);
}
}
void dfs(int n){
for(int i=1;i<=n;i++)num[i]=-1;
for(int i=1;i<=n;i++)p[i]=-1;
ti=1;
for(int i=1;i<=n;i++)
if(num[i]==-1)
vis(i,-1,n);
}
void calc(int n){
int i,j;
for(i=1;i<=n;i++){
if(p[i]==-1){
int il=0;
for(j=1;j<=n;j++)if(d[i][j])il++;
if(il>1)r[i]=1;
}
else{
int il=0;
for(j=1;j<=n;j++)
if(l[j]>=num[i]&&d[i][j])il++;
if(il)r[i]=1;
}
}
}
main()
{
int i,u,v,n,ile,j,c;
while(1){
if(scanf("%d",&ile)!=1)break;
if(ile==0)break;
for(i=0;i<=ile;i++)
for(j=0;j<=ile;j++)d[i][j]=0;
for(i=0;i<ile;i++){
scanf("%d",&u);
if(!u)break;
while(1){
if((c=fgetc(stdin))=='\n')break;
else if(c==' ')continue;
else ungetc(c,stdin);
scanf("%d", &v);
d[u][v]=d[v][u]=1;
}
}
for(i=1;i<=ile;i++)r[i]=0;
dfs(ile);
calc(ile);
int res=0;
for(i=1;i<=ile;i++)if(r[i])res++;
printf("%d\n",res);
}
return 0;
}
Code: Select all
8
2 4 5
1 3
2 4 7
1 5 6 8 7 3
1 4 6
5 4 8
3 4
4 6
0
8
2
1 3
2 4 5 6
3 7 8
3
3
4 8
4 7
0
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
5
2
3
4
5
0
5
2 3 4 5
3 1
2 1
1 5
1 4
0
6
2 3
1 4
1 4 5
2 3 6
3 5
4 5
0
9
1 2
2 3
2 5
5 4 6 8
7 8
9 8
0
3
1 2
3 2
0
2
2 1
0
3
2
3
0
6
2 3
1 4
1 4 5
2 3 6
3 6
4 5
0
5
3 2
1 3
1 2 4 5
3 5
3 4
0
Code: Select all
0
3
1
2
3
1
0
4
1
0
1
0
1
Code: Select all
Number of Articulaion point=0
2 3 4
Number of Articulaion point=3
1
Number of Articulaion point=1
1 2
Number of Articulaion point=2
2 3 4
Number of Articulaion point=3
1
Number of Articulaion point=1
Number of Articulaion point=0
2 3 5 6
Number of Articulaion point=4
2
Number of Articulaion point=1
Number of Articulaion point=0
2
Number of Articulaion point=1
Number of Articulaion point=0
3
Number of Articulaion point=1
Code: Select all
5
3 2
1 3
1 2 4 5
3 5
3 4
0Code: Select all
1Code: Select all
3
Number of Articulaion point=1
Code: Select all
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int node;
bool W[100][100];
bool mark[100];
int drop;
void check(int in)
{
int j;
mark[in]=1;
for(j=0;j<node;j++)
if(drop!=j && W[in][j] && !mark[j])
check(j);
}
int main(void)
{
char x[100];
char * pch;
bool t;
int from,to,i,j,count;
while(cin>>node && node!=0)
{
cin.get();
for(i=0;i<node;i++)
for(j=0;j<node;j++)
W[i][j]=0;
while(cin.getline(x,100))
{
pch=strtok(x," ");
from=atoi(pch);
if(from==0)break;
pch=strtok(NULL," ");
while(pch!=NULL)
{
to=atoi(pch);
W[from-1][to-1]=1;
W[to-1][from-1]=1;
pch=strtok(NULL," ");
}
}
count=0;
for(drop=0;drop<node;drop++)
{
for(j=0;j<node;j++)
mark[j]=0;
check((drop+1)%node);
t=1;
for(j=0;j<node;j++)
if(drop!=j && !mark[j])t=0;
if(t)
count++;
}
cout<<node-count<<endl;
}
return 0;
}