Pagini recente » Cod sursa (job #2685157) | Cod sursa (job #1444839) | Cod sursa (job #37615) | Cod sursa (job #1308499) | Cod sursa (job #2369831)
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v1[Nmax], v2[Nmax], v3[Nmax];
int seen[Nmax];
stack <int> st;
int n, m, x, y;
int num_ctc = 0;
vector <int> ::iterator it;
void first_DFS(int node)
{
seen[node] = 1;
for ( int i = 0, l = v1[node].size() ; i < l ; i ++ )
{
int nnode = v1[node][i];
if( seen[nnode] != 0)
continue;
first_DFS(nnode);
}
st.push(node);
}
void second_DFS(int node)
{
seen[node] = -1;
for ( int i = 0, l = v2[node].size(); i < l ; i ++ )
{
int nnode = v2[node][i];
if( seen[nnode] == -1 )
continue;
second_DFS(nnode);
}
v3[num_ctc].push_back(node);
}
int main()
{
f >> n >> m ;
while ( m -- )
{
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
for ( int i = 1 ; i <= n ; i ++ )
if(!seen[i])
first_DFS(i);
while(!st.empty())
{
if( seen[st.top()] == -1 )
{
st.pop();
continue;
}
num_ctc++;
second_DFS(st.top());
st.pop();
}
g << num_ctc << '\n';
for ( int i = 1 ; i <= num_ctc ; i ++ )
{
for ( it = v3[i].begin() ; it != v3[i].end() ; it ++ )
g << *it << " ";
g << '\n';
}
return 0;
}