Pagini recente » Cod sursa (job #2448589) | Cod sursa (job #2815693) | Cod sursa (job #1374682) | Cod sursa (job #2338529) | Cod sursa (job #2281504)
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector<int> graph[NMAX];
vector<int> transposed[NMAX];
vector<int> components[NMAX];
stack<int> stacc;
bool visited[NMAX];
int N, M;
void DFS(int vertex)
{
if(visited[vertex])
return;
visited[vertex] = 1;
for(auto y:graph[vertex])
{
DFS(y);
}
stacc.push(vertex);
}
void DFSP(int vertex, int paint)
{
if(visited[vertex])
return;
visited[vertex] = 1;
components[paint].push_back(vertex);
for(auto y:transposed[vertex])
{
DFSP(y,paint);
}
}
int main()
{
int a,b;
fi>>N>>M;
for(int i = 1; i <= M; ++i)
{
fi>>a>>b;
graph[a].push_back(b);
transposed[b].push_back(a);
}
for(int i = 1; i <= N; ++i)
{
DFS(i);
}
memset(visited, 0, N+10);
int d = 0;
for(;!stacc.empty();)
{
int tp = stacc.top();
stacc.pop();
DFSP(tp,++d);
}
int k = 0;
for(int i = 1; i <= d; ++i)
{
if(components[i].size() > 0)
k++;
}
fo<<k<<"\n";
for(int i = 1; i <= d; ++i)
{
if(components[i].size() > 0)
{
for(int j = 0; j < components[i].size(); ++j)
fo<<components[i][j]<<" ";
fo<<"\n";
}
}
}