Pagini recente » Cod sursa (job #153922) | Cod sursa (job #1892826) | Cod sursa (job #1637222) | Cod sursa (job #2343600)
#include <fstream>
#include <vector>
#define MAX 3001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct plusminus{
bool plus, minus, p;
}uz[MAX];
vector <int> d[MAX];
vector <int> dintors[MAX];
vector <int> ctc[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].push_back(y);
dintors[y].push_back(x);
}
/*for(i=1;i<=n;i++)
{for(j=0;j<d[i].size();j++)
fout << d[i][j] << ' ';
fout << '\n';}
for(i=1;i<=n;i++)
{for(j=0;j<dintors[i].size();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=0;j<ctc[i].size();j++)
fout << ctc[i][j] << ' ';
fout << '\n';}
return 0;
}
void parcurgplus(int k)
{int i;
uz[k].plus = true;
for(i=0;i<d[k].size();i++)
if(!uz[d[k][i]].plus)
parcurgplus(d[k][i]);
}
void parcurgminus(int k)
{int i;
uz[k].minus = true;
for(i=0;i<dintors[k].size();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].push_back(i);
}
else
{
uz[i].plus = false;
uz[i].minus = false;
}
}
}