1241: Graph Connectivity
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 551 | 201 | Standard |
Consider a graph G formed from a large number of nodes connected by edges. G is said to be connected if a path can be found in 0 or more steps between any pair of nodes in G. For example, the graph below is not connected because there is no path from A to C.
This graph contains, however, a number of subgraphs that are connected, one for each of the following sets of nodes: {A}, {B}, {C}, {D}, {E}, {A,B}, {B,D}, {C,E}, {A,B,D}
A connected subgraph is maximal if there are no nodes and edges in the original graph that could be added to the subgraph and still leave it connected. There are two maximal connected subgraphs above, one associated with the nodes {A, B, D} and the other with the nodes {C, E}.
Write a program to determine the number of maximal connected subgraphs of a given graph.
Input and Output
The first line of input contains a single uppercase alphabetic character. This character represents the largest node name in the graph. Each successive line contains a pair of uppercase alphabetic characters denoting an edge in the graph. The sample input section contains a possible input set for the graph pictured above.
Input is terminated by a blank line.
Write in the output the number of maximal connected subgraphs.
Sample Input
E AB CE DB EC
Sample Output
2
This problem is used for contest: 119 151
#include<stdio.h>
#include<string.h>
int a[50][50];
int vis[50];
int sum;
void dfs(int step)
{
int i;
vis[step]=1;
for(i=1;i<=sum;i++)
{
if(vis[i]==0&&a[step][i]==1)
{
dfs(i);
}
}
}
int main()
{
char ch;
int i,j;
while(scanf("%c",&ch)==1)
{
getchar();
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
sum=ch-'A'+1;
char ch1,ch2;
while(scanf("%c",&ch1)==1)
{
if(ch1=='/n') break;
scanf("%c",&ch2);
getchar();
i=ch1-'A'+1;
j=ch2-'A'+1;
a[i][j]=a[j][i]=1;
}
int count=0;
for(i=1;i<=sum;i++)
{
if(vis[i]==0)
{
count++;
dfs(i);
}
}
printf("%d/n",count);
}
return 0;
}