Pagini recente » Autentificare | Cod sursa (job #2559547) | Cautari ortogonale | Cod sursa (job #1181531) | Cod sursa (job #1880149)
#include <fstream>
#include <queue>
#define NMAX 5005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int M[NMAX][NMAX], n, m, result, visited[NMAX];
void Floyd_Warshall()
{
int k, i, j;
for(k = 1 ; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(M[i][k] == 1 && M[k][j] == 1 && i != j)
M[i][j] = 1;
}
void BFS(int x)
{
queue <int> Q;
int i, v;
Q.push(x);
visited[x] = result;
while(!Q.empty())
{
v = Q.front();
Q.pop();
for(i = 1; i <= n; i++)
if(visited[i] == 0 && M[i][v] == 1 && M[v][i] == 1)
{
Q.push(i);
visited[i] = result;
}
}
}
int main()
{
int i, j, x, y;
fin >> n >> m;
for(i = 1; i <= m; i++)
{
fin >> x >> y;
M[x][y] = 1;
}
Floyd_Warshall();
for(i = 1; i <= n; i++)
if(visited[i] == 0)
{
++result;
BFS(i);
}
fout << result << '\n';
for(i = 1; i <= result; i++)
{
for(j = 1; j <= n; j++)
if(visited[j] == i)
fout << j << ' ';
fout << '\n';
}
return 0;
}