Pagini recente » Cod sursa (job #1142305) | Cod sursa (job #1451956) | Cod sursa (job #916612) | Cod sursa (job #2275098) | Cod sursa (job #2343566)
#include <fstream>
#define MAX 5001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct plusminus{
bool plus, minus, p;
}uz[MAX];
int d[MAX][MAX];
int dintors[MAX][MAX];
int ctc[MAX][MAX];
int n, m, x, y, c;
void parcurgplus(int k);
void parcurgminus(int k);
void componenta(int k);
int main()
{int i, j;
fin >> n >> m;
for(i=1;i<=m;i++)
{
fin >> x >> y;
d[x][++d[x][0]] = y;
dintors[y][++dintors[y][0]] = x;
}
/*for(i=1;i<=n;i++)
{for(j=1;j<=d[i][0];j++)
fout << d[i][j] << ' ';
fout << '\n';}
for(i=1;i<=n;i++)
{for(j=1;j<=dintors[i][0];j++)
fout << dintors[i][j] << ' ';
fout << '\n';}*/
for(i=1;i<=n;i++)
if(!uz[i].p)
{
parcurgplus(i);
//for(j=1;j<=n;j++)
//fout << uz[j].plus << ' ' << uz[j].minus << '\n';
parcurgminus(i);
//fout << '\n';
//for(j=1;j<=n;j++)
//fout << uz[j].plus << ' ' << uz[j].minus << '\n';
componenta(i);
//fout << '\n';
}
fout << c << '\n';
for(i=1;i<=c;i++)
{for(j=1;j<=ctc[i][0];j++)
fout << ctc[i][j] << ' ';
fout << '\n';}
return 0;
}
void parcurgplus(int k)
{int i;
uz[k].plus = true;
for(i=1;i<=d[k][0];i++)
if(!uz[d[k][i]].plus)
parcurgplus(d[k][i]);
}
void parcurgminus(int k)
{int i;
uz[k].minus = true;
for(i=1;i<=dintors[k][0];i++)
if(!uz[dintors[k][i]].minus)
parcurgminus(dintors[k][i]);
}
void componenta(int k)
{int i;
c++;
for(i=k;i<=n;i++)
{
if(uz[i].plus && uz[i].minus && !uz[i].p)
{
uz[i].p = true;
ctc[c][0]++;
ctc[c][ctc[c][0]] = i;
}
else
{
uz[i].plus = false;
uz[i].minus = false;
}
}
}