sink.cpp

Ex8-4 汇点问题 &laquo 问题描述： 采用邻接矩阵表示一个具有n 个顶点的图时

#include <iostream.h>
#include <fstream.h>

template<class T>
void Make2DArray(T** &x, int rows, int cols)
{
	x = new T*[rows];
	for(int i=0; i<rows; i++)
		x[i] = new T[cols];
}

void main()
{
	int n; 
	int i,j,sum=0;
	int **a;

	ifstream infile("input.txt");
	ofstream outfile("output.txt");

	infile>>n;

	Make2DArray(a, n, n);
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			infile>>a[i][j];

	i=n-1,j=0; 
	
	while(i!=j)
	{
		if(a[i][j]==0)
		{
			j++;
		}

		else 
		{
			i--;
		}
	}

	if(a[i][j]==1)
		outfile<<0;

	else 
	{
		for(j=0; j<n; j++)
		{
			if(a[i][j]==1)
			{
				sum=1;
				outfile<<0<<endl;
				break;
			}
		}

		if(sum!=1)
		{
			for(sum=0,j=0; j<n; j++)
				sum = sum+a[j][i];

			j=n-1;
			if(sum==j)
			{
				i++;
				outfile<<i<<endl;
			}
			else
				outfile<<0<<endl;
		}
	}

	outfile.close();
}