Pagini recente » Cod sursa (job #3292577) | Cod sursa (job #2517921) | Cod sursa (job #3163594) | Cod sursa (job #3205443) | Cod sursa (job #806133)
Cod sursa(job #806133)
#include<fstream>
#include<vector>
#define plus plus1
#define minus minus1
#define nmax 100007
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[nmax];
vector <int> Gt[nmax];
int N, M, nr;
bool o[nmax];
bool plus[nmax];
bool minus[nmax];
vector <int> CTC[nmax];
void read()
{
fin >>N >>M;
for(int i = 1; i <= M; i++)
{
int x, y;
fin >>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void marcheaza_plus(int x)
{
plus[x] = true;
for(int i = 0 ;i < G[x].size(); i++)
{
if(plus[G[x][i]] == false && o[G[x][i]] == false)
marcheaza_plus(G[x][i]);
}
}
void sterge(int x)
{
plus[x] = false;
for(int i = 0 ;i < G[x].size(); i++)
{
if(plus[G[x][i]] == true )
sterge(G[x][i]);
}
}
void sterge2(int x)
{
minus[x] = false;
for(int i = 0 ;i < Gt[x].size(); i++)
{
if(minus[Gt[x][i]] == false)
{
sterge2(Gt[x][i]);
}
}
}
void marcheaza_minus(int x)
{
minus[x] = true;
if(plus[x] == true)
{
CTC[nr].push_back(x);
o[x] = true;
}
for(int i = 0; i < Gt[x].size(); i++)
{
if(minus[Gt[x][i]] == false && o[Gt[x][i]] == false)
marcheaza_minus(Gt[x][i]);
}
}
int main()
{
read();
for(int i = 1; i <= N ; i++)
{
if(o[i] == false)
{
nr++;
marcheaza_plus(i);
marcheaza_minus(i);
sterge(i);
sterge2(i);
}
}
fout << nr <<'\n';
for(int i = 1; i <= nr; i++)
{
for(int j = 0 ; j < CTC[i].size(); j++)
{
fout << CTC[i][j]<<" ";
}
fout << '\n';
}
fin.close();
return 0;
}