Pagini recente » Cod sursa (job #1168593) | Cod sursa (job #304503) | Cod sursa (job #1754254) | Cod sursa (job #1396934) | Cod sursa (job #870636)
Cod sursa(job #870636)
#include <fstream>
//2
//1 2 3
//4 5 6 7 8
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");//modif
int n, m, nrc, a[4000][4000], suc[4000], pred[4000];
bool p[2000];
void df (int nod, int nrc)
{
int i;
suc[nod] = nrc;
for (i = 1; i <= n; i++)
if (a[nod][i] == 1 and suc[i] == 0) df(i,nrc);
}
void dft (int nod,int nrc) //df transpus
{
int i;
pred[nod]=nrc;
for (i = 1; i <= n; i++)
if (a[i][nod] == 1 and pred[i] == 0) dft(i,nrc);
}
int main() {
int c,i, j, x, y;
f >> n >> m;
for (i = 1; i <= m; i++)
{
f >> x >> y;
a[x][y] = 1;
}
for (i = 1; i <= n; i++)
if (suc[i]==0)
{
nrc++;
df(i,nrc);
dft(i,nrc);
for (j = 1; j <= n; j++)
if (suc[j]!=pred[j]) suc[j]=pred[j]=0;
}
g << nrc << endl;
for (c = 1; c <= nrc; c++)
{
for (i = 1; i <= n; i++)
if(suc[i]==c) g << i << ' ';
g << endl;
}
// for (i = 1; i <= n; i++) g<<suc[i]<<' ';g<<endl;
// for (i = 1; i <= n; i++) g<<pred[i]<<' ';g<<endl;
return 0;
}