Pagini recente » Cod sursa (job #3287549) | Cod sursa (job #1567948) | Cod sursa (job #1567964) | Cod sursa (job #2482452) | Cod sursa (job #2202056)
#include <iostream>
#include <fstream>
//Roy - Warshall
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
bool D[101][101];
int n, m,c[101];
void citire()
{
int x, y;
f >> n >> m;
for(int i = 1; i <= m; i++)
{
f >> x >> y;
D[x][y] = 1;
}
}
void Roy_Warshall()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
}
int nr_comp_tare_conexe()
{
int nrc = 0;
for(int i = 1; i <= n; i++)
c[i] = 0;
for(int i = 1; i <= n; i++)
if(c[i] == 0)
{
c[i] = ++nrc;
for(int j = 1; j <= n; j++)
if(c[j] == 0 && D[i][j] == 1 && D[j][i] == 1)
c[j] = nrc;
}
return nrc;
}
int main()
{
int nrc;
citire();
Roy_Warshall();
nrc=nr_comp_tare_conexe();
g << nrc <<endl;
for(int i = 1; i <= nrc; i++)
{
for(int j = 1; j <= n; j++)
if(c[j] == i)
g << j << ' ';
g << endl;
}
return 0;
}