Pagini recente » Cod sursa (job #1177226) | Cod sursa (job #1165845) | Cod sursa (job #803232) | Cod sursa (job #1570311) | Cod sursa (job #1740724)
#include <fstream>
#include <vector>
using namespace std;
void DFS (unsigned int node);
unsigned int N, M;
unsigned int x, y;
vector <unsigned int> G[10001];
unsigned int matrix[10001][10001];
bool used[10001];
unsigned int i, j, k;
unsigned int sol;
int main ()
{
ifstream fin ("ctc.in");
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> x >> y;
matrix[x][y] = 1;
}
fin.close();
for (k=1; k<=N; k++)
for (i=1; i<=N; i++)
for (j=1; j<=N; j++)
if (i!=j && matrix[i][k]!=0 && matrix[k][j]!=0 && (matrix[i][j]>matrix[i][k]+matrix[k][j] || matrix[i][j]==0))
matrix[i][j] = matrix[i][k] + matrix[k][j];
for (i=1; i<=N; i++)
for (j=1; j<=N; j++)
if (matrix[i][j] > 0)
matrix[i][j] = 1;
for (i=1; i<=N; i++)
for (j=1; j<=N; j++)
if (matrix[i][j] == 1)
{
G[i].push_back(j);
G[j].push_back(i);
}
for (i=1; i<=N; i++)
if (!used[i])
{
DFS(i);
sol++;
}
ofstream fout ("ctc.out");
fout << sol+1;
fout.close();
return 0;
}
void DFS (unsigned int node)
{
vector <unsigned int> :: iterator i;
used[node] = 1;
for (i=G[node].begin(); i!=G[node].end(); i++)
if (!used[*i])
DFS(*i);
}