TOJ 3365 ZOJ 3232 It's not Floyd Algorithm/強連通成分

It's not Floyd Algorithm
時間制限(通常/Java):1000 MS/3000 MS実行メモリ制限:65536 KByte
説明
 
When a directed graph is given, we can solve its transitive closure easily using the well-known Floyd algorithm.
But if you're given a transitive closure, can you give a corresponding directed graph with minimal edges?
 
入力
 
About 100 test cases, seperated by blank line.
First line of each case is an integer N (1<=N<=200). The followingN lines represent the given transitive closure in 0-1 matrix form, each line hasN numbers.
 
しゅつりょく
 
For each case, just output the number of minimal edges of a directed graph which has a given transitive closure.
 
サンプル入力
 

1

1



2

1 0

0 1



2

1 1

1 1



3

1 1 1

0 1 1

0 0 1

 
 
 
サンプル出力
 

0

0

2

2

 
 
 
ヒント
Transitive closure can be presented as a matrix T, where Ti,j is true if and only if there is a path from vertexi toj.
まず、縮点は、各強連通成分に対してn個の点があれば、少なくともn個のエッジだけで連通できる(n=1を除く)
それから縮み点の後の図に対してどのように1回の反閉包をして余分な辺を取り除いて統計してみます

	

#include<stdio.h>

#include<string.h>

int n;

int dfn[210];

int low[210];

bool instack[210];

int stack[210];

int cnt,num,top;

int a[210][210];

int count[210];

int belong[210];

int map[210][210];

void floyd()

{

	int i,j,k;

	for(k = 1;k <= cnt; k++)

		for(i = 1;i <= cnt; i++)

			for(j = 1;j <= cnt; j++)

				if(map[i][k] && map[k][j] && map[i][j])

					map[i][j] = 0;

}

void tarjan(int i)

{

        int j,k;

        dfn[i] = low[i] = ++num;

        instack[i] = true;

        stack[++top] = i;

        for(j = 1;j <= n; j++)

        {

            k = a[i][j];

            if(!k)

            	continue;

            if(!dfn[j])

            {

                tarjan(j);

                if(low[i] > low[j])

                	low[i] = low[j];

            }

            else if(instack[j] && low[i] > dfn[j])

                low[i] = dfn[j];

        } 

        if(low[i] == dfn[i])

        {

            cnt++;

            do

            {

                j = stack[top--];

                instack[j] = false;

                belong[j] = cnt; 

                count[cnt]++;

            }

            while(i != j);

        }

} 

int main()

{

	int i,j,sum;

	while(scanf("%d",&n)!=EOF)

	{

		for(i = 1;i <= n; i++)

			for(j = 1; j<= n; j++)

				scanf("%d",&a[i][j]);

		num = top = cnt = 0;

		memset(dfn,0,sizeof(dfn));

		memset(instack,false,sizeof(instack));

		memset(count,0,sizeof(count));

		memset(map,0,sizeof(map));

		for(i = 1;i <= n; i++)

			if(!dfn[i])

				tarjan(i);

		for(i = 1; i<= n; i++)

			for(j = 1; j<= n; j++)

				if(a[i][j])

					if(belong[i] != belong[j])

						map[belong[i]][belong[j]] = 1;

		sum = 0;

		floyd();

		for(i = 1;i <= cnt; i++)

			if(count[i] != 1)

				sum += count[i];

		for(i = 1;i <= cnt; i++)

			for(j = 1; j<= cnt; j++)

				if(map[i][j])

					sum++;

		printf("%d
",sum);

	}

	return 0;

}