Pagini recente » Cod sursa (job #1795287) | Borderou de evaluare (job #2012055) | Cod sursa (job #346256) | Cod sursa (job #1494221) | Cod sursa (job #2165907)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int N_MAX = 100000;
vector <int> g[N_MAX + 1], gt[N_MAX + 1], answer[N_MAX + 1];
stack <int> st;
bool vis[N_MAX + 1];
int ctc[N_MAX + 1];
void dfs(int node)
{
vis[node] = true;
for(int son : g[node])
if(vis[son] == false)
dfs(son);
st.push(node);
}
void dfst(int node, int nr)
{
ctc[node] = nr;
for(int son : gt[node])
if(ctc[son] == 0)
dfst(son, nr);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(vis[i] == false)
dfs(i);
int nr = 0;
while(st.empty() == false)
{
int node = st.top();
st.pop();
if(ctc[node] == 0)
{
nr++;
dfst(node, nr);
}
}
for(int i = 1; i <= n; i++)
answer[ctc[i]].push_back(i);
printf("%d\n", nr);
for(int i = 1; i <= nr; i++)
{
for(int node : answer[i])
printf("%d ", node);
printf("\n");
}
return 0;
}