Pagini recente » Cod sursa (job #1814858) | Cod sursa (job #372778) | Cod sursa (job #93014) | Cod sursa (job #2604223) | Cod sursa (job #2091992)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
int n, m, x, y, K;
bitset<100003> v;
vector<int> a[100003], inv[100003], w[100003];
stack<int> st;
ifstream F("ctc.in");
ofstream G("ctc.out");
void dfs(int x)
{
v[x] = 1;
vector<int> :: iterator it;
for( it = a[x].begin(); it != a[x].end(); ++ it )
if(!v[*it]) dfs(*it);
st.push(x);
}
void dfs1(int nod)
{
v[nod] = 1;
vector<int> :: iterator it;
for( it = inv[nod].begin(); it != inv[nod].end(); ++ it )
if(!v[*it]) dfs1(*it);
w[K].push_back(nod);
}
int main()
{
F >> n >> m;
for( int i = 1; i <= m; ++ i )
{
F >> x >> y;
a[x].push_back(y);
inv[y].push_back(x);
}
for( int i = 1; i <= n; ++ i )
if(!v[i]) dfs(i);
v = 0;
while(!st.empty())
{
x = st.top();
st.pop();
if(!v[x])
{
K++;
dfs1(x);
}
}
G << K << '\n';
vector<int> :: iterator it;
for(int i = 1; i <= K; ++ i, G << '\n')
for( it = w[i].begin(); it != w[i].end(); ++ it )
G << *it << " ";
return 0;
}