Pagini recente » Cod sursa (job #310921) | Cod sursa (job #2151665) | Cod sursa (job #833266) | Cod sursa (job #433367) | Cod sursa (job #2980027)
#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;
vector<int> la[N], li[N];
set<int> s1, s2, viz;
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 dfs(int x)
{
viz.insert(x);
s1.insert(x);
for(int i = 0; i < (int)la[x].size(); ++i)
{
int y = la[x][i];
if (!viz.count(y))
dfs(y);
}
}
void dfsi(int x)
{
viz.insert(x);
s2.insert(x);
for(int i = 0; i < (int)li[x].size(); ++i)
{
int y = li[x][i];
if (!viz.count(y))
dfsi(y);
}
}
void CTC()
{
for(int i = 1; i <= n; ++i)
if(!ctc[i])
{
++nrctc;
s1.clear();
s2.clear();
viz.clear();
dfs(i);
viz.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;
}