Pagini recente » Cod sursa (job #928858) | Cod sursa (job #2859424) | Cod sursa (job #1788596) | Cod sursa (job #1336152) | Cod sursa (job #877619)
Cod sursa(job #877619)
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 100001;
vector<int> G[MAXN];
vector<int> GT[MAXN];
stack<int> st;
vector<int> sol;
vector<vector<int> > sols;
bool dead[MAXN];
bool vis[MAXN];
bool vis_trans[MAXN];
void dfs(int node)
{
vis[node] = true;
vector<int>::iterator it;
for (it = G[node].begin(); it != G[node].end(); ++it) {
if (dead[*it] || vis[*it])
continue;
dfs(*it);
}
st.push(node);
}
void dfs_trans(int node)
{
sol.push_back(node);
vis_trans[node] = true;
dead[node] = true;
vector<int>::iterator it;
for (it = GT[node].begin(); it != GT[node].end(); ++it) {
if (dead[*it] || vis_trans[*it])
continue;
dfs_trans(*it);
}
}
void components()
{
while (!st.empty()) {
int node = st.top();
st.pop();
if (dead[node])
continue;
sol.clear();
dfs_trans(node);
sols.push_back(sol);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
GT[y].push_back(x);
}
memset(dead, false, sizeof(dead));
memset(vis, false, sizeof(vis));
memset(vis_trans, false, sizeof(vis_trans));
for (int i = 1; i <= n; ++i) {
if (!dead[i] && !vis[i]) {
dfs(i);
components();
}
}
printf("%lu\n", sols.size());
for (int i = 0; i < sols.size(); ++i) {
vector<int>::iterator it;
for (it = sols[i].begin(); it != sols[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}