Pagini recente » Cod sursa (job #501257) | Cod sursa (job #1187015) | Cod sursa (job #209119) | Cod sursa (job #2068931) | Cod sursa (job #1962575)
#include <fstream>
#include <vector>
#include <stack>
const int NMAX = 100005;
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M;
int x, y;
vector <int> v[NMAX];
vector <int> vt[NMAX];
stack <int> S;
bool visited[NMAX];
vector <int> sols[NMAX];
int num_sol;
void print()
{
g << num_sol << '\n';
for (int i = 0; i < num_sol; ++i)
{
for (int j = 0; j < sols[i].size(); ++j)
{
g << sols[i][j] << " ";
}
g << '\n';
}
}
void DFS(int node)
{
visited[node] = true;
for (int i = 0; i < v[node].size(); ++i)
{
int neigh = v[node][i];
if (!visited[neigh])
{
DFS(neigh);
}
}
S.push(node);
}
void DFSt(int node)
{
sols[num_sol].push_back(node);
visited[node] = false;
for (int i = 0; i < vt[node].size(); ++i)
{
int neigh = vt[node][i];
if (visited[neigh])
{
DFSt(neigh);
}
}
}
void solve()
{
for (int i = 1; i <= N; ++i)
{
if (!visited[i])
{
DFS(i);
}
}
while(!S.empty())
{
int node = S.top();
S.pop();
if (visited[node])
{
DFSt(node);
num_sol++;
}
else
{
S.pop();
}
}
}
void read()
{
f >> N >> M;
for (int i = 1; i <= M; ++i)
{
f >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
}
int main()
{
read();
solve();
print();
}