Pagini recente » Cod sursa (job #2277676) | Cod sursa (job #1562476) | Cod sursa (job #194417) | Cod sursa (job #176294) | Cod sursa (job #1187279)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long int64;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100010;
int N, M;
int where[NMAX];
vector<int> Gr[NMAX], GrT[NMAX], result[NMAX], discovered;
bitset<NMAX> used;
int main()
{
int x, y, i, j, edge, _edge, value = 0;
queue<int> Q;
fin >> N >> M;
while(M--)
{
fin >> x >> y;
Gr[x].push_back(y);
GrT[y].push_back(x);
}
for (i = 1; i <= N; ++i)
{
if (used[i]) continue;
Q.push(i);
used[i] = true;
discovered.push_back(i);
while(!Q.empty())
{
edge = Q.front(), Q.pop();
for (j = 0; j < (int)Gr[edge].size(); ++j)
{
_edge = Gr[edge][j];
if (used[_edge]) continue;
Q.push(_edge);
used[_edge] = true;
discovered.push_back(_edge);
}
}
}
reverse(discovered.begin(), discovered.end());
fill_n(where + 1, N, -1);
for ( ; discovered.size(); discovered.pop_back())
{
if (where[discovered.back()] != -1) continue;
where[discovered.back()] = value;
Q.push(discovered.back());
while(!Q.empty())
{
edge = Q.front(), Q.pop();
for (j = 0; j < (int)GrT[edge].size(); ++j)
{
_edge = GrT[edge][j];
if (where[_edge] != -1) continue;
where[_edge] = value;
Q.push(_edge);
}
}
++value;
}
for (i = 1; i <= N; ++i)
result[where[i]].push_back(i);
fout << value << '\n';
for (i = 0; i < value; ++i)
{
for (j = 0; j < (int)result[i].size(); ++j)
fout << result[i][j] << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}