Pagini recente » Cod sursa (job #878759) | Cod sursa (job #2884670) | Cod sursa (job #1663073) | Cod sursa (job #2878776) | Cod sursa (job #2980041)
#include <fstream>
#include <set>
#include <vector>
using namespace std;
#define PB push_back
#define N 100001
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, ctc[N], nrctc, viz[N];
vector<int> la[N], li[N];
set<int> s1, s2;
void citire()
{
in >> n >> m;
for (int i = 0; i < m; ++i)
{
unsigned int x, y;
in >> x >> y;
la[x].PB(y);
li[y].PB(x);
}
in.close();
}
void V_clear()
{
for(int i = 1; i <= n; ++i)
viz[i] = 0;
}
void dfs(int x)
{
viz[x] = 1;
s1.insert(x);
for(int i = 0; i < (int)la[x].size(); ++i)
{
int y = la[x][i];
if (!viz[y] && !s1.count(y))
dfs(y);
}
viz[x] = 0;
}
void dfsi(int x)
{
viz[x] = 1;
s2.insert(x);
for(int i = 0; i < (int)li[x].size(); ++i)
{
int y = li[x][i];
if (!viz[y] && !s2.count(y))
dfsi(y);
}
viz[x] = 0;
}
void CTC()
{
for(int i = 1; i <= n; ++i)
if(!ctc[i])
{
++nrctc;
s1.clear();
s2.clear();
//V_clear();
dfs(i);
//V_clear();
dfsi(i);
for(set<int> :: iterator it = s1.begin(); it != s1.end(); ++it)
{
int x = *it;
if(s2.count(x))
ctc[x] = nrctc;
}
}
}
int main()
{
citire();
CTC();
out << nrctc << '\n';
for(int i = 1; i <= nrctc; ++i)
{
for(int j = 1; j <= n; ++j)
if(ctc[j] == i)
out << j << ' ';
out << '\n';
}
return 0;
}